题意：
Alice和Bob两个好朋含友又开始玩取石子了。游戏开始时，有N堆石子排成一排，然后他们轮流操作（Alice先手），
每次操作时从下面的规则中任选一个：
1：从某堆石子中取走一个
2：合并任意两堆石子
不能操作的人输。Alice想知道，她是否能有必胜策略
T<=100, N<=50. ai<=1000
思路：From https://blog.csdn.net/sunshinezff/article/details/50893626?utm_source=blogkpcl10
考虑如果不存在石子数为1的堆。
设这种状态下操作数为x,显然x等于石子总数加操作数减1。
可以证明当x为奇数时先手必胜。当x为偶数时先手必败。
如果只有1堆石子，该结论显然成立。
如果有多堆石子,每堆石子个数都大于1，并且x为偶数,下面我们证明这样先手必败。
1.如果先手选择合并两堆石子,那么每堆石子的个数依然大于1,x变为奇数。
2.如果先手选择从一堆石子数大于2的堆中拿走一枚石子,那么同上每堆石子个数依然大于1,x变为奇数。
3.如果先手选择从一堆石子数等于2的堆中拿走一枚石子,那么后手可以合并剩下的1枚石子到任意一个堆。
那样x的奇偶性不变,每堆石子的个数依然大于1.
综上所述，结论成立。
然后考虑如果存在石子数为1的堆.我们设石子数为1的堆的个数为x,其余堆的个数为y.
令f[x][y]为这种状态下先手必胜或是必败。
每次转移枚举所有可能的操作。记忆化搜索即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 typedef long long ll; 7 using namespace std; 8 #define N 210000 9 #define oo 10000000 10 #define MOD 1000000007 11 12 int f[60][51000]; 13 14 int dfs(int a,int b) 15 { 16 if(b==1) return dfs(a+1,0); 17 if(a==0) return b&1; 18 if(f[a][b]!=-1) return f[a][b]; 19 if(a&&!dfs(a-1,b)) return f[a][b]=1; //拿1 20 if(a&&b&&!dfs(a-1,b+1)) return f[a][b]=1; //将1和大于1的合并 21 if(a>=2&&!dfs(a-2,b+2+(b?1:0))) return f[a][b]=1; //合并2堆1 22 if(b&&!dfs(a,b-1)) return f[a][b]=1; //合并2堆大于1的或拿1个大于1的 23 return f[a][b]=0; 24 } 25 26 int main() 27 { 28 memset(f,-1,sizeof(f)); 29 int cas; 30 scanf("%d",&cas); 31 while(cas--) 32 { 33 int n; 34 scanf("%d",&n); 35 int a=0; 36 int b=-1; 37 for(int i=1;i<=n;i++) 38 { 39 int x; 40 scanf("%d",&x); 41 if(x==1) a++; 42 else b+=x+1; 43 } 44 b=max(b,0); 45 if(dfs(a,b)) printf("YES "); 46 else printf("NO "); 47 } 48 return 0; 49 } 50