题解 P2575 【高手过招】

· · 题解

一道优秀的阶梯Nim+SG定理。

首先，我们在整个序列前面加上一个空格（设此时空格个数为C+1），然后从右到左将所有空格编号为0至C。令第i级阶梯上的棋子数为编号为i的空格右边的连续棋子个数。

以下用■表示棋子，□表示空格。则对于这个场景：

(□)□■□□□□□□□□□□□□□□□□■■（样例第一组数据）

有第0至17级阶梯（容易数出有18个空格）棋子个数分别是\{2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0\}。

将一个棋子移至右边第一个空格时，相当于将其与其右边相邻的所有棋子移到下一级阶梯。如这样：

(□)□■□□□□□□□□□□□□□□□□■■变成

(□)□□■□□□□□□□□□□□□□□□■■时相当于

$\{2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0\}$（第$16$层一颗棋子下移一级阶梯），又如： (□)■■■□□■变成 (□)■□■■□■时相当于 $\{1,0,3\}$变成 $\{1,2,1\}$（第$2$层两颗棋子下移一级阶梯）。 我们发现，当所有棋子都在第$0$级阶梯时，先手无法操作，必败。 ### 这不是典型的阶梯Nim吗？ 于是我们处理一下，用阶梯Nim的解法（SG函数为奇数位异或和）再加一个SG定理处理多行即可。 $Code: 
#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;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])
                {
                    if((--cnt)&1)ans1^=tot;//奇数级阶梯，异或
                    tot=0;
                }
                else ++tot;//加棋子到阶梯上
            }
            ans2^=ans1;//SG定理应用
        }
        if(ans2)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}