题目链接

题目介绍

就是给一个n乘m大小的纸片，两个人轮流剪纸，每次只能顺着横线或者竖线剪，最后先剪到1*1大小纸片的人获胜。

题目理解

（参考蓝书）实际上就是一个二维版本的NIM游戏，最后的获胜条件不是传统的不能动获胜，变成了1x1局面获胜。首先确定必败条件：必须认识到，剪成1xX或者Xx1的情况是不存在的（因为另一个人一定会将剩下的纸片剪成1*1，因此两个人都会避免剪成这种情况）。那么，必败条件即为当纸片为2x2、2x3、3x2共三种情况，将其SG函数值定义为0。接下来就是利用已经计算的SG值更新其他SG值，一层层异或上去就行了，获胜条件是所有子局面异或结果大于0.

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 200 + 10;
const int mod = 1e9 + 7;
int sg[N][N];

inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

int calsg(int n, int m) {
    if (sg[n][m] != -1) return sg[n][m];
    int vis[N];
    memset(vis, 0, sizeof vis); // 记录哪些子局面被访问到了，最后用于计算MEX操作的值
    for (int i = 2; i <= n - i; i++) { // 不从1开始访问，因为1没意义，是必败局面，没有人会愿意剪成1*x或者x*1的
        vis[calsg(i, m) ^ calsg(n - i, m)] = 1;
    }
    for (int i = 2; i <= m - i; i++) {
        vis[calsg(n, i) ^ calsg(n, m - i)] = 1;
    }
    sg[n][m] = 0;
    while (vis[sg[n][m]]) sg[n][m]++; // 从小到大找到第一个（最小的）使得vis=0的值，也就是Mex运算的定义
    sg[m][n] = sg[n][m];
    return sg[n][m]; // 谁是宽谁是长不重要
}

void solve() {
    int n, m;
    memset(sg, -1, sizeof sg);
    sg[2][3] = sg[3][2] = sg[2][2] = 0;
    while (cin >> n >> m) {
        if (calsg(n, m) > 0) cout << "WIN" << endl; // 只要最后sg函数值为0就是必败局面，否则就是必胜局面（定理）
        else cout << "LOSE" << endl;
    }
}

int main() {
    solve();
    return 0;
}