Cutting Game

最近博弈论专题，感觉自己没了。。。（果然借了智商高利贷迟早是要还的 ）

首先我们发现，切割过后的纸片是可以单独考虑的。

我们再分析一下题意。

首先，面对只要有一边长为1的纸片，我就一定会赢。

而且，题目说的是切割出的任意纸片！！！这就意味着假设一张纸被切成了1和2，后手切了1，我还可以继续切2！！！（我在这个地方理解了半天才懂，这就是语文考D的人呐 ）

这就符合我们的sg函数。（其实是因为我知道这是sg ）

既然是二维的sg，就枚举行与列的分界线就行了。

等等先别走。当你开开心心码完发现，，，样例都过不了？？

我们还忽略了一点：当你的分割中出现了一边长为1的纸片就赢不了了。其实这是因为这道题与基本模型有点点不一样：取石子是强制要求石子全取完的，也就是如果有两个必胜态，先手反而会输。但这道题是只要割到\((1,1)\)就直接结束了，就像是你本来在做活动时想攒很多钱买辅xiao 导huang 书，但攒完后发现活动没辽。因为根本不符合性质，显然我们就不能从一边为1的状态转移了。

上马吗？马比车快哟。

#include<cstdio>
#include<cstring>

int n, m;
bool vis[1002];
int sg[205][205];

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) > '9' || s < '0') if(s == '-') f = -1;
    while(s >= '0' && s <= '9') {
        x = (x << 1) + (x << 3) + (s ^ 48);
        s = getchar();
    }
    return x * f;
}

int main() {
    for(int i = 1; i <= 200; ++ i) {
        for(int j = 1; j <= 200; ++ j) {
            memset(vis, 0, sizeof vis);
            for(int k = 2; k <= j - 2; ++ k) vis[sg[i][k] ^ sg[i][j - k]] = 1;
            for(int k = 2; k <= i - 2; ++ k) vis[sg[k][j] ^ sg[i - k][j]] = 1;
            for(int k = 0; ; ++ k) if(! vis[k]) {sg[i][j] = k; break;}
        }
    }
    while(scanf("%d %d", &n, &m) != EOF) {
        puts(sg[n][m] ? "WIN" : "LOSE");
    }
    return 0;
}

Cutting Game

原文：https://www.cnblogs.com/AWhiteWall/p/12326530.html