自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 21:39:15，当前版本为作者最后更新于2019-05-22 09:11:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道优秀的阶梯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,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;
}