HDU 5724 Chess（SG函数+状态压缩）

http://acm.split.hdu.edu.cn/showproblem.php?pid=5724

题意：

现在有一个n*20的棋盘，上面有一些棋子，双方每次可以选择一个棋子把它移动到其右边第一个空位置处，谁不能移动了谁就输。

思路：

找规律好像找不着，那么就考虑SG函数了，因为一共只有20列，所以可以状态压缩处理，这样就可以方便的得到某个状态的后继状态。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
11 using namespace std;
12 typedef long long ll;
13 typedef pair<int,int> pll;
14 const int INF = 0x3f3f3f3f;
15 const int maxn = 50 + 5;
16 
17 int n;
18 int SG[1<<21],vis[25];
19 
20 void get_SG()
21 {
22     for(int state=0;state<(1<<20);state++)
23     {
24         memset(vis,0,sizeof(vis));
25         int last = -1;  //空位置
26         for(int i=0;i<20;i++)
27         {
28             if(state & (1<<i))
29             {
30                 if(last==-1)  continue;
31                 int nextstate = state^(1<<i)^(1<<last);
32                 vis[SG[nextstate]]=1;
33             }
34             else last=i;
35         }
36         for(int i=0;;i++)  if(!vis[i])
37         {
38             SG[state]=i;
39             break;
40         }
41     }
42 }
43 
44 int main()
45 {
46     //freopen("in.txt","r",stdin);
47     get_SG();
48     int T;
49     scanf("%d",&T);
50     while(T--)
51     {
52         scanf("%d",&n);
53         int ans=0;
54         for(int i=1;i<=n;i++)
55         {
56             int num; scanf("%d",&num);
57             int state = 0;
58             while(num--)
59             {
60                 int x; scanf("%d",&x);
61                 state|=1<<(20-x);
62             }
63             ans^=SG[state];
64         }
65         if(ans)  puts("YES");
66         else puts("NO");
67     }
68     return 0;
69 }