Chess (SG + 状态压缩预处理)

#include<bits/stdc++.h>
#define bit(t) (1 << t)
using namespace std;const int maxn = <<;
const int k = ;//k是集合s的大小
int sg[maxn];//sg[n] n表示每堆数量
bool vis[];void get_sg(){
int maxm = <<;
for(int sta = ; sta < maxm; sta ++){
// printf("**%d**\n",sta);
memset(vis, , sizeof(vis));
for(int i = ; i >= ; i --){
if(sta & bit(i))
for(int j = i - ; j >= ; j --){
if(sta & bit(j))continue;
int tmp = sta;
tmp |= bit(j);
tmp &= (~bit(i));
vis[sg[tmp]] = true;
break;
}
}
for(int i = ; i < ; i ++)
if(!vis[i]){
sg[sta] = i;break;
} }
}int main()
{
get_sg();
int T,n,m,a,sta;scanf("%d",&T);
while(T --){
int goal = ;
scanf("%d",&n);
while(n --){
scanf("%d",&m);
sta = ;
while(m--){
scanf("%d",&a);
sta |= ( << ( - a));
}
goal ^= sg[sta];
}
printf("%s\n",goal?"YES":"NO");
}
}