题意：
1 × n 个格子，每人每次选一个格子打上叉（不得重复），如果一个人画完叉后出现了连续的三个叉，则此人胜。
给n，判断先手胜还是先手败。
思路：
假设选择画叉的位置是i，则对方只能在前[1,i-3]中或[i+3,n]中选择画叉。子问题出现。
根据SG的定义，即可求出SG(N)。看代码。
代码：
int sg[2005]; int n; int dfs(int n){ if(n<0) return 0; if(sg[n]!=-1) return sg[n]; bool g[2005] = {0}; rep(i,1,n){ int t=dfs(i-3)^dfs(n-i-2); g[t]=true; } for(int i=0;;++i){ if(!g[i]) return sg[n]=i; } } int main(){ mem(sg,-1); while(scanf("%d",&n)!=EOF){ dfs(n); rep(i,0,n) printf("sg[%d]=%d\n",i,sg[i]); if(sg[n]==0) puts("2"); else puts("1"); } }
poj 3537 Crosses and Crosses （SG）
原文：http://www.cnblogs.com/fish7/p/4004690.html