C++-POJ2234-Matches Game[Nim][SG函数]

 1 #include <set>
 2 #include <map>
 3 #include <cmath>
 4 #include <queue>
 5 #include <vector>
 6 #include <cstdio>
 7 #include <cstdlib>
 8 #include <cstring>
 9 #include <iostream>
10 #include <algorithm>
11 using namespace std;
12 const int MAXM=21;
13 int m,a[MAXM],sg[MAXM];
14 //对于所有的sg[x]状态先默认为0，即必败
15 //sg(x)=mex{sg(y)|y是x的后继}
16 //即sg(y)集合中，未出现的最小非负整数
17 //这里利用xor异或的特殊性质，将sg(x)=sg(y1)^...^sg(yk)
18 //sg(x)>0为必胜，sg(x)=0为必败 
19 int main(){
20     while(scanf("%d",&m)!=EOF){
21         memset(sg,0,sizeof(sg));
22         for(int i=1;i<=m;i++)scanf("%d",&a[i]);
23         for(int i=1;i<=m;i++)sg[i]=sg[i-1]^a[i];
24         puts(sg[m]?"Yes":"No");
25     }
26     return 0;
27 }