NIM博弈游戏，SG函数---zoj_3084,zoj_2083

        Nim游戏是两个人进行的游戏有如下规则：

       1)桌子上有 N 堆石子，游戏者轮流取石子。

       2)每次只能从一堆中取出任意数目的石子，但不能不取。

       3)取走最后一个石子者胜。

       为了求解这一类问题，我们通常要引出SG函数和游戏和的概念

       SG函数：对于单一游戏的某一个状态u,sg(u)=mex(sg(v)|从状态u通过游戏的一步到大状态v), 其中，mex（minimal excludant）是定义在整数集合上的操作。它的自变量是任意整数集合，函数值是不属于该集合的最小自然数。 通常来说，当游戏者无法作出行动的时候（无路可走），该状态的sg值为0；sg值为0的状态是必败状态

       下面给出SG函数的性质：

          （1）对于任意的局面，如果它的 SG 值为 0，那么它的任何一个后继局面的SG 值不为0； 
          （2）对于任意的局面，如果它的 SG 值不为 0，那么它一定有一个后继局面的 SG值为0。

       游戏的和：考虑任意多个同时进行的 SG-组合游戏，这些 SG-组合游戏的和是这样一个 SG-组合游戏，在它进行的过程中，游戏者可以任意挑选其中的一个单一游戏进行决策，最终，没有办法进行决策的人输。

       我们引入游戏和的目的是为了把组合游戏转化为单一游戏分别求解SG值，最后只需求出所有单一游戏SG值的异或即可。证明这里就不写了，国家队论文里有三篇可以参考

       对于Nim游戏，可以把K堆石子的每一堆看成是一个简单的游戏，分别求出每一堆的SG值，最后求异或即可，显然每一堆的SG值为每一堆中石子的数量。

zoj_3084:

变异的Nim游戏，只能取规定个数的石子，用记忆搜索求每堆的SG值即可,注意visit开的大小

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int k,m,l,s[101],h[101],sg[10005];
int res[105];
void init()
{
	memset(res,0,sizeof(res));
	memset(sg,-1,sizeof(sg));
	sg[0]=0;
	return;
}
/*void cal_sg(int a)
{
	bool visit[10005];
	memset(visit,0,sizeof(visit));
	for(int i=0;i<k;++i)
	{
		if(a-s[i]>=0)
		visit[sg[a-s[i]]]=1;
	}
	for(int i=0;i<10005;++i)
	{
		if(!visit[i])
		{
			sg[a]=i;
			return;
		}
	}	
}*/
int cal_sg(int a)
{
	if(sg[a]!=-1)
		return sg[a];
	bool visit[80];
	memset(visit,0,sizeof(visit));
	for(int i=0;i<k;++i)
	{
		if(a-s[i]>=0)
		{
			cal_sg(a-s[i]);
			visit[sg[a-s[i]]]=1;
		}
	}
	for(int i=0;i<10005;++i)
	{
		if(!visit[i])
		{
			sg[a]=i;
			break;
		}
	}
	return sg[a];
}
int main()
{
	freopen("e:\\zoj\\zoj_3084.txt","r",stdin);
	while(scanf("%d",&k)&&k!=0)
	{
		for(int i=0;i<k;++i)
			scanf("%d",&s[i]);
		init();
		scanf("%d",&m);
		for(int i=0;i<m;++i)
		{
			scanf("%d",&l);
			for(int j=0;j<l;++j)
			{
				scanf("%d",&h[j]);
			}
			for(int j=0;j<l;++j)
			{
				res[i]^=cal_sg(h[j]);
			}
			/*if(res)
				printf("W");
			else
				printf("L");*/
		}
		for(int i=0;i<m;++i)
		{
			if(res[i])
				printf("W");
			else
				printf("L");
		}
		puts("");
	}
}

 

ZOJ_2083:

类似Nim,但是变成了线段染色，很巧妙！当一个线段被染成两部分时，分别求出这两部分的SG值再求异或即可

#include<cstdio>
#include<string.h>
using namespace std;
int n,sg[51];
void init()
{
	sg[0]=0;
	sg[1]=0;
}
void cal_sg(int k)
{
	int visit[51];
	memset(visit,0,sizeof(visit));
	for(int i=0;i<=k-2;++i)
	{
		visit[sg[i]^sg[k-i-2]]=1;	
	}
	for(int i=0;i<51;++i)
	{
		if(!visit[i])
		{
			sg[k]=i;
			return;
		}
	}
}
int main()
{
	init();
	for(int i=2;i<51;++i)
		cal_sg(i);
	freopen("e:\\zoj\\zoj_2083.txt","r",stdin);
	while(scanf("%d",&n)!=EOF)
	{
		int a,res;
		res=0;
		for(int i=0;i<n;++i)
		{
			scanf("%d",&a);
			res^=sg[a];
		}
		if(res)
			puts("Yes");
		else
			puts("No");
	}	
}