又是多校的一道所谓签到题:但是感觉还是有难度的: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;
}