HDOJ 5724 Chess

又是多校的一道所谓签到题：但是感觉还是有难度的：HDOJ 5724

是一道典型的sg博弈打表的题

sg函数和NIM游戏已经解释得够多的了，现在就只分析这个题目

需要分阶段：一行一个阶段，然后把所有的sg值异或起来

然后呢，需要对每一行进行分析，因为最多20列，所以可以提前打表弄好，也可以用-1作为访问标记，来记忆化搜索

如何得到sg值？就需要对题意分析，如何得到后继状态？

后继：把一个棋子移到右边的空格子，或者是一个棋子，跳过右边相邻的棋子，进入相邻的空格

所以就是检测一个有棋子的格子，和一个没有棋子的格子，然后与原理状态异或，则变成了新状态（也就是后继状态）

见代码：

（打表的写法）

#include<bits/stdc++.h>
using namespace std;

const int maxn=21;
int sg[1<<maxn];

int getsg(int x){
	bool mex[maxn<<1];
	memset(mex,false,sizeof(mex));
	for(int i=20;i>=0;i--){
		if (x&(1<<i))
			for(int j=i-1;j>=0;j--)
				if (!(x&(1<<j))){
					int tmp=x^(1<<i)^(1<<j);
					mex[sg[tmp]]=true;
					break;
				}
	}
	for(int i=0;;i++)
		if (!mex[i]) return i;
}

int main(){
	//freopen("input.txt","r",stdin);
	memset(sg,0,sizeof(sg));
	int maxnum=(1<<20);
	for(int i=0;i<maxnum;i++)
		sg[i]=getsg(i);
	int T,n,m,x,ans,temp;
	scanf("%d",&T);
	while(T--){
		ans=0;
		scanf("%d",&n);
		while(n--){
			scanf("%d",&m);
			temp=0;
			while(m--){
				scanf("%d",&x);
				temp=temp|(1<<(20-x));
			}
			ans^=sg[temp];
		}
		printf("%s\n",ans?"YES":"NO");
	}
	return 0;
}

记忆化搜索的写法：

#include<bits/stdc++.h>
using namespace std;

const int maxn=21;
int sg[1<<maxn];

int getsg(int x){
	if (sg[x]!=-1) return sg[x];
	bool mex[maxn<<1];
	memset(mex,false,sizeof(mex));
	for(int i=20;i>=0;i--){
		if (x&(1<<i))
			for(int j=i-1;j>=0;j--)
				if (!(x&(1<<j))){
					int tmp=x^(1<<i)^(1<<j);
					mex[getsg(tmp)]=true;
					break;
				}
	}
	for(int i=0;;i++)
		if (!mex[i]) return sg[x]=i;
}

int main(){
	//freopen("input.txt","r",stdin);
	memset(sg,-1,sizeof(sg));
	int T,n,m,x,ans,temp;
	scanf("%d",&T);
	while(T--){
		ans=0;
		scanf("%d",&n);
		while(n--){
			scanf("%d",&m);
			temp=0;
			while(m--){
				scanf("%d",&x);
				temp=temp|(1<<(20-x));
			}
			ans^=getsg(temp);
		}
		printf("%s\n",ans?"YES":"NO");
	}
	return 0;
}