uva 10561 - Treblecross(Nim)

uva 10561 - Treblecross(Nim)

題目鏈接：uva 10561 - Treblecross

題目大意：n個格子排成一排，其中一些格子有'X',兩個游戲者輪流操作，在格子中放X，如果此時出現連續3個X，則獲勝。給出先手是否可以取勝，取勝方案的第一步該怎麼走。

解題思路：一個X可以導致左右兩個的兩個格子都不能再放X，因為如果出現XX.、.XX、X.X，那麼下一個人肯定勝利。所以對於長度為n的格子序列，g(x)=maxg(x?3),g(x?4)...g(2)XORg(n?7).
所以可以預先處理出g數組，然後對於給定的序列，枚舉先手下的位置，判斷這種情況下，後手是否為必敗態。注意如果先手一步即可勝利要特殊考慮。

 #include 
#include 
#include 

using namespace std;
const int maxn = 200;

int g[maxn+5], v[maxn+5];

int SG (int s) {
    memset(v, 0, sizeof(v));

    for (int i = 1; i <= s; i++) {
        int t = 0;
        if (s - i - 2 >= 0)
            t ^= g[s-i-2];
        if (i - 3 >= 0)
            t ^= g[i-3];
        v[t] = 1;
    }
    int mv = -1;
    while (v[++mv]);
    return mv;
}

void init () {
    memset(g, 0, sizeof(g));
    g[1] = g[2] = g[3] = 1;
    for (int i = 4; i <= 200; i++)
        g[i] = SG(i);
}

int n, len, pos[maxn+5];
char str[maxn+5];

bool check () {
    int pre = -3, ret = 0;

    for (int i = 0; i <= len; i++) {
        if (str[i] == 'X') {
            if (i - pre <= 2)
                return false;
            int l = max(i - pre - 5, 0);

            if (l)
                ret ^= g[l];
            pre = i;
        }
    }

    int l = max(len - pre - 3, 0);
    if (l)
        ret ^= g[l];
    return ret == 0;
}

bool judge () {
    n = 0;
    len = strlen(str);


    for (int i = 0; i < len; i++) {
        if (str[i] == '.') {
            str[i] = 'X';
            if (check())
                pos[n++] = i + 1;
            str[i] = '.';
        }

        if (i && i < len - 1 & str[i-1] == 'X' && str[i+1] == 'X')
                pos[n++] = i + 1;

        if (i < len - 2 && str[i+1] == 'X' && str[i+2] == 'X')
            pos[n++] = i + 1;

        if (i >= 2 && str[i-1] == 'X' && str[i-2] == 'X')
            pos[n++] = i + 1;
    }
    return n;
}

int main () {
    init();
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%s", str);
        printf("%s\n", judge() ? "WINNING" : "LOSING");

        if (n)
            printf("%d", pos[0]);
        for (int i = 1; i < n; i++)
            printf(" %d", pos[i]);
        printf("\n");
    }
    return 0;
}