如果已经有三个相邻的X，则先手已经输了。
如果有两个相邻的X或者两个X相隔一个.，那么先手一定胜。
除去上面两种情况，每个X周围两个格子不能再放X了，因为放完之后，对手下一轮再放一个就输了。
最后当“禁区”布满整行，不能再放X了，那个人就输了。
每放一个X，禁区会把它所在的线段“分割”开来，这若干个片段就可以看做若干个游戏的和。
设g(x)表示x个连续格子对应的SG函数值，递推来求g(x)：
g(x) = mex{ g(x-3), g(x-4), g(x-5), g(x-6) xor g(1), g(x-7) xor g(2)... }
g(0) = 0, g(1) = g(2) = g(3) = 1
枚举策略时，就是模拟下一步的状态，记录其中所有必败状态。
1 #include2 #include 3 4 const int maxn = 200; 5 char s[maxn + 10]; 6 int g[maxn + 10], ans[maxn + 10]; 7 bool vis[maxn + 10]; 8 9 bool winning(const char* s)10 {11 int n = strlen(s);12 for(int i = 0; i < n-2; i++)//已经有三个相邻的X，先手输13 if(s[i] == 'X' && s[i+1] == 'X' && s[i+2] == 'X') return false;14 15 bool no[n+1];16 memset(no, false, sizeof(no));17 for(int i = 0; i < n; i++) if(s[i] == 'X')18 {19 for(int d = -2; d <= 2; d++)20 {21 if(i+d >= 0 && i+d < n)22 {23 if(d != 0 && s[i+d] == 'X') return true;//有两个X在彼此的禁区，先手胜24 no[i+d] = true;//设置禁区25 }26 }27 }28 29 no[n] = 1;30 int sg = 0;31 for(int i = 0; i < n; i++)32 {33 if(no[i]) continue;34 int cnt = 0;35 while(i < n && !no[i]) { i++; cnt++; }36 sg ^= g[cnt];37 }38 return sg != 0;39 }40 41 int main()42 {43 //freopen("in.txt", "r", stdin);44 45 g[0] = 0;46 g[1] = g[2] = g[3] = 1;47 for(int i = 4; i <= maxn; i++)48 { //递推求函数g49 memset(vis, false, sizeof(vis));50 for(int j = 3; i-j >= 0; j++)51 {52 int v = 0;53 v ^= g[i-j];54 int x = j - 5;55 if(x > 0) v ^= g[x];56 vis[v] = true;57 58 for(int j = 0; ; j++) if(!vis[j]) { g[i] = j; break; }59 }60 }61 62 int T;63 scanf("%d", &T);64 while(T--)65 {66 scanf("%s", s);67 if(!winning(s)) { printf("LOSING\n\n"); continue; }68 69 puts("WINNING");70 int n = strlen(s);71 memset(ans, 0, sizeof(ans));72 int p = 0;73 for(int i = 0; i < n; i++) if(s[i] == '.')74 {75 s[i] = 'X';76 if(!winning(s)) ans[p++] = i+1;//后继必败状态便是先手下一步的策略77 s[i] = '.';78 }79 for(int i = 0; i < p; i++)80 {81 if(i) printf(" ");82 printf("%d", ans[i]);83 }84 printf("\n");85 }86 87 return 0;88 }