题目描述
AKN玩游戏玩累了，于是他开始和同伴下棋了，玩的是跳棋！对手是wwx！这两位上古神遇在一起下棋，使得棋局变得玄幻莫测，高手过招，必有一赢，他们都将用最佳策略下棋，现在给你一个n*20的棋盘，以及棋盘上有若干个棋子，问谁赢？akn先手！

游戏规则是这样的：

对于一个棋子，能将它向右移动一格，如果右边有棋子，则向右跳到第一个空格，如果右边没有空格，则不能移动这个棋子，如果所有棋子都不能移动，那么将输掉这场比赛。
样例输入：

2
1
2 19 20
2
1 19
1 18

输出：

NO
YES

题意：

这个题我看了一阵子才明白题意，每个棋子只能想右走，当走到头（也就是第20格）就不能再移动了，当右边的格已经有棋子时，可以跳过这个棋子走到下一个格，但是如果这个棋子右边没有格那就不能走了，就比如样例第一个例子，19 20两个紧挨着的棋子，位于棋盘最后，就都移动不了

题解：

经典博弈论
我看到两个做法：

方法一.

我们先考虑120的情况
如果我们将所有空格编号，将空格之间相连的棋子看做一层，什么意思？就是我们将连续的块看做一层，不连续的看做不同层，这样从左到右形成x层，然后所有棋子要向右移，就是从上层向下层移动，当全部移动到第0层，也就是最后，游戏结束
这样问题就变成了阶梯nim问题
在阶梯nim问题中，我们只需要考虑位置为奇数的ai的异或和
在本题中，我们只需要考虑层数为奇数的棋子数量
求出120的答案后，将所有答案异或就是最终答案(sg定理)

代码：

#include<cstdio>
#include<cstring>
int T,N,K,cnt,tot,x,ans1,ans2;
bool hv[23];//hv[i]==true表示i位置有石子
int main()
{
    scanf(" %d",&T);
    while(T--)
    {
        scanf(" %d",&N);
        ans2=0;//整个数据的SG值用ans2储存
        while(N--)
        {
            scanf(" %d",&K);
            memset(hv,false,sizeof(hv));
            cnt=20-K+1;//空格数量+1 
            tot=0;
            ans1=0;//cnt即C,tot储存当前阶梯棋子个数，ans1储存本行SG值
            while(K--)
            {
                scanf(" %d",&x);
                hv[x]=true;//标记有石子
            }
            for(int i=1;i<=20;++i)
            {
                if(!hv[i])//如果是空格 
                {
                    cnt--;//空格数量减1 
                    if((cnt)&1)ans1^=tot;//奇数级阶梯，异或
                    tot=0;
                }
                else ++tot;//加棋子到阶梯上
            }
            ans2^=ans1;//SG定理应用
        }
        if(ans2)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

方法二：

sg函数大家应该都知道
对于任意一个状态x，如果sg(x)=0说明x为必败态，!=0为必胜态
sg(x)为不属于其所有后续状态的sg函数值集合的最小非负整数
sg(x)=mex(S),其中S是x的后续状态的sg函数值集合
比如x有5个后续状态，其中sg函数值分别是1,5,2,0,4，那么sg(x)=3
对于棋盘的状态，我们完全可以用二进制来表示，比如10001，表示第1位和第5位有棋子
题目中有20个位置，我们规定最右边的位置是第0位，最左边是第19位
对于题目给的每种状态x，我们一次寻找x的后续状态S的值，然后利用sg(x)=mex(S)的结论得到答案
那怎么查找x的后续状态S?
我们从x状态的最高位开始，如果第i格有棋子，我们就让该棋子移动到第i-1格上，也就是让当前棋子向后移动一位，依次递归，当然第0位的就不用移动
如果有两个棋子靠着也没事，按照我们的设计，最右边的棋子会向右移动，这样两个棋子就不靠着了

代码：

#include<iostream>
#include<cstring>
#define MAXN (1<<20)-1
using namespace std;

int sg[MAXN+5];

int dfs(int x){
    //cout<<x<<endl;
    if(sg[x]!=-1) return sg[x];

    bool vis[25];
    memset(vis, 0, sizeof(vis));

    int last0 = -1;
    for(int i=0;i<20;i++){
        if((x>>i)&1){
            if(last0==-1) continue;
            vis[dfs(x^(1<<i)^(1<<last0))] = 1;
        }
        else last0 = i;
    }

    for(int i=0;i<20;i++){
        if(!vis[i]) return sg[x] = i;
    }
}

int main(){
    memset(sg,-1,sizeof(sg));

    int T,N,m;
    int t;
    cin>>T;
    while(T--){
        int ans = 0;
        cin>>N;
        for(int i=1;i<=N;i++){
            int x = 0;
            cin>>m;
            while(m--){
                cin>>t;
                x += (1<<(20-t));
            }
            ans ^= dfs(x);
        }
        //cout<<ans;
        if(ans) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

    return 0;
}