题意：

给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; } 
   
  

?