题意:有一个数组,Alice和Bob每次拿走其中的一个数,Alice先拿,问最后Alice拿的数的和是否为偶数
Solution
博弈论,这里的数据量不大,dp+记忆化搜索
dp[cnt1][cnt2][c][s]表示剩余cnt1个奇数和cnt2个偶数时,当前的操作人为c,Alice拿的数为奇数或者偶数
1 int dfs(int cnt1,int cnt2,int p,int sum) 2 { 3 if(dp[cnt1][cnt2][p][sum]!=-1)return dp[cnt1][cnt2][p][sum]; 4 if(cnt1==0&&cnt2==0) 5 { 6 if(p==0)return sum==0; 7 else return sum!=0; 8 } 9 int res=0; 10 if(p==0) 11 { 12 if(cnt1)res|=!dfs(cnt1-1,cnt2,p^1,sum^1); 13 if(cnt2)res|=!dfs(cnt1,cnt2-1,p^1,sum); 14 }else 15 { 16 if(cnt1)res|=!dfs(cnt1-1,cnt2,p^1,sum); 17 if(cnt2)res|=!dfs(cnt1,cnt2-1,p^1,sum); 18 } 19 return dp[cnt1][cnt2][p][sum]=res; 20 } 21 22 void solve() 23 { 24 memset(dp,-1,sizeof(dp)); 25 int n;cin>>n; 26 int cnt1=0,cnt2=0; 27 int temp=n; 28 while(temp--) 29 { 30 int x;cin>>x; 31 if(x&1)cnt1++; 32 else cnt2++; 33 } 34 if(dfs(cnt1,cnt2,0,0))cout<<"Alice\n"; 35 else cout<<"Bob\n"; 36 37 }