每天一道博弈论之“高手过招”（非口胡）

   题目大意：

  给你一个n行20列的棋盘，上面有一些棋子

  每个棋子只能往右边第一个空格处移动，无棋子可移动即判定为输

  现在给你棋盘大小和棋子分布，问先手是否必胜

    题解：

   可以看出每行是独立的，也就是说只要求出每行的SG函数值，在亦或一下就可以了（SG定理^_^）

   又由于每行长度一样，所以可以预处理每个状态的SG值

   把每个的状态对应成一个二进制数，就能方便地求出SG值了qaq

 题目来源：https://www.luogu.org/problemnew/show/P2575

（今天有代码哦qwq）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1000 + 10 ;

inline int read() {
    int k = 0 , f = 1 ; char c = getchar() ;
    for( ; !isdigit(c) ; c = getchar())
      if(c == '-') f = -1 ;
    for( ; isdigit(c) ; c = getchar())
      k = k*10 + c-'0' ;
    return k*f ;
}

int sg[1<<20] ;
bool vis[28] ;

inline void solve(int x) {
    memset(vis,0,sizeof(vis)) ;
    int nxt = 0, ww = 1 ;
    for(int i=1;i<=20;i++) {
        if(x&ww) {
             if(nxt) vis[sg[x^ww^(1<<(nxt-1))]] = 1 ;
        } else nxt = i ;
        ww <<= 1 ;
    }
    for(int i=0; ;i++) {
        if(!vis[i]) {
            sg[x] = i ; return ;
        } 
    }
}

int main() {
    int t = read(), mm = (1<<20) ;
    for(int i=0;i<mm;i++) solve(i) ;
    int n, m, ans, x, tmp ;
    while(t--) {
        ans = 0 ;
        n = read() ;
        for(int i=1;i<=n;i++) {
            m = read() ; tmp = 0 ;
            for(int j=1;j<=m;j++) {
                x = read() ;
                tmp += (1<<(20-x)) ;
            }
            ans ^= sg[tmp] ;
        }
        if(ans) printf("YES
") ;
        else printf("NO
") ;
    }
    return 0 ;
}