2022杭电第一场

• 1011 Random

  • 题意：
  • 思路：
  • 代码：

• 1012 Alice and Bob

  • 题意：
  • 思路：
  • 代码：

1011 Random

题意：

从[0,1]随机生成n个数，进行m次操作，有$\frac{1}{2}\backslash frac\{1\}\{2\}$概率删除最大值，$\frac{1}{2}\backslash frac\{1\}\{2\}$概率删除最小值。求剩下的n-m个随机数的和的期望值。

思路：

由于每个数是[0,1]的随机数，期望为$\frac{1}{2}\backslash frac\{1\}\{2\}$，又最终一定剩下n-m个数，则最终的答案就是$\frac{n-m}{2}\backslash frac\{n-m\}\{2\}$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll t,n,m;
ll kpow(ll a,ll b){
if(b==0) return 1;
    if(b%2==1) return a*kpow(a,b-1)%mod;
    else {
        ll t=kpow(a,b/2);
        return t*t%mod;                                            }
}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
    if(n<=m) cout<<0<<endl;
    else 
        cout<<(n-m)%mod*kpow(2,mod-2)%mod<<endl;    
    }
}

1012 Alice and Bob

题意：

黑板上有m个数，每个数在0~n之间。Alice在黑板上没出现0的情况下把黑板上的数分为两组，然后Bob可以选择一组数字删除，剩下的一组每个数减1，重复这一过程。如果黑板上出现0，则Alice获胜；若黑板上的数全被删除，则Bob获胜。

思路：

游戏相当于Alice先手，考虑如何分组让Alice必胜，其他情况Bob获胜。对于$ii$（1~n）这个数字，我们用等价的方式每两个$ii$，相当于1个$i-1i-1$。从n到1遍历，判断0的个数是否大于0。 另外，用cin,cout要关同步流。

代码：

using namespace std;
typedef long long ll;
int t,n;
int a[1000006];

void solve(){

        scanf("%d",&n);
        
        for(int i=0;i<=n;i++)
        {
            cin>>a[i];
        }
        
        
        for(int i=n;i>=1;i--){
            a[i-1]+=a[i]/2;
        }
        
        if(a[0]) printf("Alice\n");
        else printf("Bob\n");
}
int main(){
    scanf("%d",&t);
    while(t--){
        solve();
    }
}