G60 有向图游戏 SG函数【博弈论】

边界：把 2×2、2×3 和 3×2 作为最终的必败态。

子节点：整张纸看做根节点，成对拆分的子图之间不是独立的，因为它们是一次操作得到的，所以把两子图的 sg(s₁) ⊕ sg(s₂) 作为配对子节点的 sg 值。

SG函数公式：sg(n, m) = mex({sg(i, m) ⊕ sg(n - i, m), 2 ≤ i ≤ n - 2} ∪ {sg(n, i) ⊕ sg(n, m - i), 2 ≤ i ≤ m - 2})

#include <bits/stdc++.h>
using namespace std;

const int N = 210;
int n, m;
int f[N][N];

int sg(int a, int b)
{
    // 记忆化搜索
    if (f[a][b] != -1) return f[a][b];
    // 把子节点的sg值插入集合
    set<int> S;
    for (int i = 2; i <= a - 2; i++)
        S.insert(sg(i, b) ^ sg(a - i, b));
    for (int i = 2; i <= b - 2; i++)
        S.insert(sg(a, i) ^ sg(a, b - i));
    // mex运算求当前节点的sg值并记忆
    for (int i = 0;; i++)
        if (!S.count(i))
            return f[a][b] = f[b][a] = i;
}
int main()
{
    memset(f, -1, sizeof f);
    while (cin >> n >> m)
        puts(sg(n, m) ? "WIN" : "LOSE");
    return 0;
}

G60 有向图游戏 SG函数【博弈论】

边界：把 $2 \times 2$、$2 \times 3$ 和 $3 \times 2$ 作为最终的必败态。
子节点： 整张纸看做根节点，成对拆分的子图之间不是独立的，因为它们是一次操作得到的，所以把两子图的 $sg(s_1) \oplus sg(s_2)$ 作为配对子节点的 $sg$ 值。
$sg(n, m) = mex\left(\{sg(i, m) \oplus sg(n - i, m), 2 \leq i \leq n - 2\}\right.\left.\cup \{sg(n, i) \oplus sg(n, m - i), 2 \leq i \leq m - 2\}\right)$

#include <bits/stdc++.h>
using namespace std;

const int N = 210;
int n, m;
int f[N][N];

int sg(int a, int b)
{
    // 记忆化搜索
    if (f[ a ][ b ] != -1) return f[ a ][ b ];
    // 把子节点的sg值插入集合
    set<int> S;
    for (int i = 2; i <= a - 2; i++)
        S.insert(sg(i, b) ^ sg(a - i, b));
    for (int i = 2; i <= b - 2; i++)
        S.insert(sg(a, i) ^ sg(a, b - i));
    // mex运算求当前节点的sg值并记忆
    for (int i = 0;; i++)
        if (!S.count(i))
            return f[ a ][ b ] = f[ b ][ a ] = i;
}
int main()
{
    memset(f, -1, sizeof f);
    while (cin >> n >> m)
        puts(sg(n, m) ? "WIN" : "LOSE");
    return 0;
}