poj 3537Crosses and Crosses 博弈論之grundy值

poj 3537Crosses and Crosses 博弈論之grundy值

題意：

給1*n的格子，輪流在上面叉叉，最先畫得3個連續叉叉的贏，問先手必勝還是必敗。

分析：

求狀態的grundy值（也就是sg值），具體怎麼求詳見代碼，為什麼這麼求要自己想的，只可意會（別人都說去看game theory，呵呵）。

代碼：

//poj 3537
//sep9
#include 
#include 
using namespace std;
int grundy[2048];
int h[2048];
int get_grundy(int n)
{
	if(n<0)
		return 0;
	if(grundy[n]!=-1)
		return grundy[n];	
	int h[2048];
	memset(h,0,sizeof(h));
	for(int i=1;i<=n;++i){
		int t=get_grundy(i-3)^get_grundy(n-i-2);
		h[t]=1;
	}
	int i;
	for(i=0;h[i];++i);
	return grundy[n]=i;			
}
int main()
{
	int n;
	memset(grundy,-1,sizeof(grundy));
	grundy[0]=0,grundy[1]=1,grundy[2]=1,grundy[3]=1;
	while(scanf("%d",&n)==1)
		if(get_grundy(n)!=0)
			puts("1");
		else
			puts("2");
	return 0;	
}