P10501 Cutting Game 题解

· · 题解

因为是多测，所以直接预处理出 SG 函数。

求一个 m \times n 的纸片的 SG 值时，枚举横着切和竖着切的每一种切法。纸片 SG 值就是所有切法 SG 值的 mex。

一种切法的 SG 值是切开两块的 SG 值异或和。

但是和一般的有向图游戏不同的是，这个游戏在切出一个“只有一个格网的纸片” 时就会直接结束游戏，而不需要等对手把其他的子游戏也解决。

所以在游戏结束时会是大量的 2 \times 2，2 \times 3 这种必败状态。在枚举切法时需注意不能切出宽度为 1 的条。

#include <bits/stdc++.h>
using namespace std;
int sg[202][202];
bool f[202];
int n,m;
signed main () {
    sg[1][1] = 0;
    for (int i = 2;i <= 200;i++) {
        sg[1][i] = 1;
        sg[i][1] = 1;
    }
    for (int i = 2;i <= 200;i++) {
        for (int j = 2;j <= 200;j++) {
            memset(f,0,sizeof(f));
            for (int k = 2;k < i - 1;k++) {
                f[sg[k][j] ^ sg[i - k][j]] = 1;
            }
            for (int k = 2;k < j - 1;k++) {
                f[sg[i][k] ^ sg[i][j - k]] = 1;
            }
            for (int k = 0;k <= 200;k++) {
                if (!f[k]) {
                    sg[i][j] = k;
                    break;
                }
            }
        }
    }
    while (cin >> n >> m) {
        if (sg[n][m]) {
            cout << "WIN" << endl;
        } else {
            cout << "LOSE" << endl;
        }
    }
    return 0;
}