题目大意：
n*20的棋盘，每行有若干个棋子。对于一个棋子，能将它向右移动一格，如果右边有棋子，则向右跳到第一个空格，如果右边没有空格，则不能移动这个棋子，如果所有棋子都不能移动，那么将输掉这场比赛。
解题思路：
根据题意可知每行进行操作都是独立的，所以整个游戏又可分为n个子游戏，这是sg定理的第一步。
下一步考虑每个子游戏的状态。可知当棋子紧邻着排在左边的时候为必败态，而其他状态的后继可以通过枚举每个棋子向右走一步得到。这样通过sg解题就差最后一步如何表示状态了，每行只有20个固定的格子，每个格子只有有无棋子两种状态，于是就可以直接上二进制压缩了。
代码：
//bug1:递归过程中使用stl爆栈导致tle
//bug2:递归参数使用全局数组导致数值紊乱wa
//bug3:寻找mex值时未考虑后继状态sg值会重复导致wa
//bug4:忽略else会和最临近的if对应导致结构错误
//以上bug已全部修复
#include <bits/stdc++.h>
#define int long long
#define BS 1048576
using namespace std;
int sg[2000005];
int dfs(int x)
{
if(sg[x]!=-1) return sg[x];
int a[25],cnt=0;
memset(a,-1,sizeof(a));
//从右到左第i个位置
for(int i=1;i<=20;i++)
{
int next=x; //next代表后继状态
if(((x>>(i-1))&1)){ //如果第i个位置为1
next^=(1<<(i-1));
int j=i-1;
while(j>0&&((x>>(j-1))&1)) j--; //寻找右边第一个为0的位置
if(j==0) continue;
else{
next^=(1<<(j-1));
cnt++;
a[cnt]=dfs(next);
}
}
}
sort(a+1,a+1+cnt);
if(a[1]!=0) return sg[x]=0;
for(int i=2;i<=cnt;i++)
{
if(a[i]-a[i-1]>1) return sg[x]=a[i-1]+1;
}
return sg[x]=a[cnt]+1;
}
int t,n,m;
int temp;
signed main()
{
memset(sg,-1,sizeof(sg));
for(int i=0;i<=20;i++) sg[(1<<i)-1]=0;
//for(int i=1;i<=BS;i++) sg[i]=dfs(i);
scanf("%lld",&t);
while(t--)
{
int xorSum=0;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&m);
int now=0;
for(int j=1;j<=m;j++)
{
scanf("%lld",&temp);
now|=(1<<(20-temp));
}
xorSum^=dfs(now);
}
if(xorSum==0) printf("NO\n");
else printf("YES\n");
}
return 0;
}
先介绍以下阶梯nim：
模型：n堆石子每次可以从i堆中取走若干个放到i-1层，或者从第1层直接拿走若干个。
决策：奇数位的异或和是否为0。
证明：如下图所示，两人可通过轮流操作使所有偶数堆石子全部扔掉，总局面等价于只有奇数堆有石子，而一个人可以移动奇数堆的石子到偶数堆中，偶数堆有相当于无效堆，所以即相当于直接从奇数堆中取石子，就转化为了所有奇数堆的普通nim游戏。
而在本题中：
我们可以将每个空格左边连续的棋子数看作一堆石子，而最左端贴近边界的棋子因为不能移动，可以看作证明过程中“从第一堆石子中取走的石子”，即不计入石子堆中，这样因为空格的数量是固定的，所以石子堆数也是固定的了。而每部移动都可以模拟成“从第i堆石子取走一部分放到第i-1堆中”（如果不理解自己手动画点小样例就懂了）。那么这道题就是一道裸的sg定理+阶梯nim了。
代码：
#include <bits/stdc++.h>
using namespace std;
int t,n,m;
int temp,a[21];
int main()
{
scanf("%d",&t);
while(t--)
{
int xorSum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&m);
bool visited[21];
memset(visited,false,sizeof(visited));
for(int j=1;j<=m;j++)
{
scanf("%d",&temp);
visited[temp]=true;
}
int cnt=0,last=0;
for(int j=1;j<=20;j++)
{
if(visited[j]){
last++;
}else{
cnt++;
a[cnt]=last;
last=0;
}
}
for(int i=cnt;i>0;i-=2) xorSum^=a[i];
}
if(xorSum==0) printf("NO\n");
else printf("YES\n");
}
return 0;
}
谨以本篇博客记录笔者wa了一天的暴力sg。。。。
