UVA 11534 - Say Goodbye to Tic-Tac-Toe

题目链接

题意：给定一个序列，轮流放XO，要求不能有连续的XX或OO，最后一个放的人赢，问谁赢

思路：sg函数，每一段...看成一个子游戏，利用记忆化求sg值，记忆化的状态要记录下左边和右边是X还是O即可

代码：

#include 
  
   
#include 
   
     const int N = 105; int t, sg[3][3][N]; char str[N]; int getnum(char c) { if (c == 'X') return 1; if (c == 'O') return 2; } int mex(int s, int e, int l) { if (sg[s][e][l] != -1) return sg[s][e][l]; if (l == 0) return sg[s][e][l] = 0; bool vis[N]; memset(vis, false, sizeof(vis)); for (int i = 1; i <= l; i++) { for (int j = 1; j <= 2; j++) { if (i == 1 && s == j) continue; if (i == l && e == j) continue; int t = mex(s, j, i - 1)^mex(j, e, l - i); vis[t] = true; } } for (int i = 0; ;i++) if (!vis[i]) return sg[s][e][l] = i; } int main() { memset(sg, -1, sizeof(sg)); scanf("%d", &t); while (t--) { scanf("%s", str); int len = strlen(str), s = 0, e = 0, l = 0, ans = 0, cnt = 0; for (int i = 0; i < len; i++) { if (str[i] == '.') l++; else { e = getnum(str[i]); ans ^= mex(s, e, l); s = e; l = 0; cnt++; } } ans ^= mex(s, 0, l); if (cnt&1) ans = (ans == 0?1:0); printf("%s\n", ans?"Possible.":"Impossible."); } return 0; }