博弈论嘻嘻

https://www.cnblogs.com/Simon-X/p/5905960.html 

这个介绍得很好，生动形象得介绍了sg。

http://hihocoder.com/contest/hiho46/problem/1 这个呢就是官方点得解释，emmm我选择上面那个

chess hdu 5724

题意：有一个n行20列的棋盘，棋盘上分布着一些棋子，A、B两人轮流下棋，A先手，每次操作可以将某个棋子放到自己右边的第一个空位（也就是说右边如果已经有子，可以跳过它，没有就右移一步），但最多20列，绝对不能超过棋盘，无棋可走的输。

题解：进行状态压缩，bit来表示在一行中一个点有没有棋子，有棋子为1，没有棋子为0，0到（2^20-1）就代表全了所有的可能。

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

int SG[(1<<20)+100],book[30];

void get_SG()
{
    for(int i=0;i<(1<<20);i++)
    {
        memset(book,-1,sizeof(book));

        int last=-1;
        for(int j=0;j<20;j++)
        {
            if(!((i>>j)&1)) ///空格在最右的位置
                last=j;
            if((i>>j)&1)   ///最右棋子的位置
            {
                if(last!=-1)
                    book[SG[(i^(1<<j))^(1<<last)]]=true; ///后继状态标记
            ///找到最右边的棋子以及可移动的空格，然后互换成后继并标记，互换后一定比互换前的值小，因为我们是先找空格再找棋子的
            ///
            }
        }

        int item=0;
        while(book[item]!=-1) item++; ///找出最小的不属于这个集合的非负整数

//        printf("item=%d\n",item);
        SG[i]=item;
    }
}
int main()
{
    memset(SG,0,sizeof(SG));
    get_SG();


    int ncase;
    scanf("%d",&ncase);

    while(ncase--)
    {
        int n,m,ans=0,item;

        scanf("%d",&n);

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&m);
            item=0;

            for(int j=1;j<=m;j++){
                int x;
                scanf("%d",&x);

                item^=1<<(20-x);
            }
//            printf("%d\n",SG[item]);
            ans^=SG[item];
        }
//    printf("ans=%d\n",ans);
        if(ans) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}