往模型上靠。。
普通 NIM 是：所有堆都到终态为负。这里是：任意一堆移动到终态为胜。
那么在新问题里，我们要避免走到任意一个可以移动到终态的状态。（否则下一步就输了）
我们定义这样的状态的 sg=0，同时避免从这些状态转移，这样就和普通的 NIM 靠上了。

//}/* .................................................................................................................................. */

const int N = int(1e2) + 9;

int sg[N][N];

int mex(set<int>& H){
    REP(i, H.size()+1) if (!CTN(H, i)) return i;
    assert(0);
    return -1;
}

void init(){
    REP_2(i, j, N, N){
        if (!i || !j || i == j) sg[i][j] = -1;
        else{
            set<int> H;
            REP_1(k, i) H.insert(sg[i-k][j]);
            REP_1(k, j) H.insert(sg[i][j-k]);
            REP_1(k, min(i, j)) H.insert(sg[i-k][j-k]);
            sg[i][j] = mex(H);
        }
    }
}

bool win(){
    int SG = 0;
    Rush{
        int x, y; RD(x, y); if (!x && !y) return false;
        if (sg[x][y] == -1) return true;
        SG ^= sg[x][y];
    }
    return SG;
}

int main(){
    
#ifndef ONLINE_JUDGE
    freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    init(); Rush puts(win() ? "^o^" : "T_T");
}

http://www.lydsy.com/JudgeOnline/problem.php?id=1457

[衡阳八中1457 棋盘游戏]【博弈】【SG函数】【NIM和】【任意一子游戏到达终态结束的游戏】

Posted by xiaodao
Category: BZOJ