这里有2种方法：
方法一：求SG函数
sg[i][j]:i表示1的个数，j表示合并操作的步数。
这共有4种操作：
1.消除一个1；
2.减掉一个1；
3.合并2个1；
4.把1合并到另外不是1中。
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
int dp[][];
int dfs(int a,int b)
{
if(dp[a][b]!=-) return dp[a][b];
if(b==) return dp[a][b]=dfs(a+,);
dp[a][b]=;
if(a>=&&!dfs(a-,b)) dp[a][b]=;
else if(b>=&&!dfs(a,b-)) dp[a][b]=;
else if(a>=&&((b>=&&!dfs(a-,b+))||(b==&&!dfs(a-,)))) dp[a][b]=;
else if(a>=&&b>=&&!dfs(a-,b+)) dp[a][b]=;
return dp[a][b];
}
int main(){
int i,t,ca=,n,k,one,other;
memset(dp,-,sizeof(dp));
scanf("%d",&t);
while(t--){
scanf("%d",&n);
other=one=;
for(i=;i<n;i++){
scanf("%d",&k);
if(k==) one++;
else other+=k+;
}
if(other) other--;
int ff=dfs(one,other);
printf("Case #%d: ",++ca);
if(ff) puts("Alice");
else puts("Bob");
}
return ;
}
方法二：
可以分四种情况：
1.只有1的时候，1的个数为3的倍数则必输否则赢；
2.只有1个2和若干1时，1的个数为3的倍数则必输否则赢；
3.其他情况，计算总和+个数-1，如果是奇数则必赢否则输；
4.剩下的就赢了。
代码如下：
#include<stdio.h>
#define I(x) scanf("%d",&x)
int main(){
int i,t,n,s,k,j=,m;
bool f;
I(t);
while(t--){
I(m);
for(s=n=f=i=;i<m;i++){
I(k);
if(k==) n++;
s+=k;
}
if(n==m) f=n%;
else if(s-n==) f=n%;
else if((s+m-)&) f=;
else f=n&;
printf("Case #%d: ",++j);
puts(f?"Alice":"Bob");
}
return ;
}