AcWing P2575. 博弈论
原题链接
简单
作者:
Lemmon_kk
,
2020-08-16 18:50:36
,
所有人可见
,
阅读 556
// 有向图游戏的和
// 高手过招
// 不要用set 会tle
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;
const int N = (1 << 20) + 10;
int n, m, t;
int ans;
int sg[N];
int dfs(int x){
if(sg[x] != -1) return sg[x];
bool vis[25]; memset(vis, 0, sizeof vis);
int last0 = -1;
for(int i = 19;i >= 0;i -- ){
if(x >> i & 1){
if(last0 == -1) continue;
vis[dfs(x ^ (1 << i) ^ (1 << last0))] = true;
}else last0 = i;
}
int mex;
for(mex = 0;;mex ++ )
if(!vis[mex]) break;
return sg[x] = mex;
}
int main(){
memset(sg, -1, sizeof sg);
scanf("%d", &t);
while(t -- ){
ans = 0;
scanf("%d", &n);
for(int i = 1;i <= n;i ++ ){
int state = 0, col;
scanf("%d", &m);
while(m -- ){
scanf("%d", &col);
col -- ;
state += (1 << col);
}
ans ^= dfs(state);
}
if(ans) puts("YES");
else puts("NO");
}
return 0;
}