首页 > 代码库 > 【POJ3537】Crosses and Crosses 博弈,SG函数,Multi-SG博弈

【POJ3537】Crosses and Crosses 博弈,SG函数,Multi-SG博弈

转载请注明出处:http://blog.csdn.net/vmurder/article/details/42654067

其实我就是觉得原创的访问量比未授权盗版多有点不爽233。。。

题意:有个一维棋盘,两人轮流下棋,然后谁连成三个谁赢。


题解:

我们考虑到一个长度为n的棋盘,在i处下子,相当于把游戏转化成两个游戏GAME(x-i-2)和GAME(i-3)。


原因:左边一部分将不再能下子,右边一部分将不再能下子(准确地说是两个)。

然后就成了当前状态俩子状态,然后就是裸SG转移了。

Multi-SG博弈就是指一个游戏可以转化成俩子游戏。


代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2015
using namespace std;
int sg[N];
int SG(int x)
{
	if(x<0)return 0;
	if(sg[x]+1)return sg[x];
	bool vis[N]={0};
	int i;
	for(i=1;i<=x;i++)vis[SG(x-i-2)^SG(i-3)]=true;
	for(i=0;vis[i];i++);
	return sg[x]=i;
}
int main()
{
//	freopen("test.in","r",stdin);
	memset(sg,-1,sizeof sg);
	sg[0]=0,sg[1]=sg[2]=sg[3]=1;
	for(int x;scanf("%d",&x)!=EOF;)
		printf("%d\n",SG(x)?1:2);
	return 0;
}



【POJ3537】Crosses and Crosses 博弈,SG函数,Multi-SG博弈