?

题目大意：

两人在1*N的格子上轮流画X，每一次可以在空白的格子上画X，如果一个玩家把三个X连起来，那么就获胜。你的任务是判断是先手胜还是后手。

思路：

在纸上画画你会发现，你画一个格子后，他的左边两个和右边两个是不能画的（如果存在） ，也就是说，你每画一次，那么就排除掉5个格子

所以分为左边i - 3和右边n- i- 2两个部分。用SG函数求解。

?

?

#include
  
   
#include
   
     const int MAXN = 2000 + 10; int sg[MAXN]; int dfs(int n) { if (n < 0) return 0; if (sg[n] != -1) return sg[n]; bool vis[MAXN]; memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) { vis[dfs(i - 3) ^ dfs(n - i - 2)] = 1; } for (int i = 0; i<=n; i++) { if (!vis[i]) return sg[n] = i; } } int main() { int n; memset(sg, -1, sizeof(sg)); while (~scanf(%d, &n)) { printf(%d , dfs(n) == 0 ? 2 : 1); } return 0; }
   
  

?