poj.org/problem?id=3537 (题目链接)
题意
给出一个1*n的棋盘，每次可以选择一个没被标记过的点打标记，若经过某一步操作使得出现3个连续的标记，则最后操作的人获胜。问是否存在先手必胜策略。
Solution
我们可以很快发现，若给x位置打上标记，那么棋盘就被分成了2份，分别是x-3以及n-x-2，于是${sg[n]=mex\{sg[x-3]~XOR~sg[n-x-2]}\}$，1<=x<=n。因为n<=2000，直接暴力求解sg函数即可。
代码
// poj3537
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=2010;
int n,sg[maxn]; int cal(int x) {
if (x<0) return 0;
if (sg[x]!=-1) return sg[x];
bool vis[maxn];
memset(vis,0,sizeof(vis));
for (int i=1;i<=x;i++)
vis[cal(i-3)^cal(x-i-2)]=1;
for (int i=0;;i++) if (!vis[i]) return sg[x]=i;
}
int main() {
int n;
scanf("%d",&n);
memset(sg,-1,sizeof(sg));
if (cal(n)) printf("1");
else printf("2");
return 0;
}