P10501 Cutting Game

· · 题解

P10501 Cutting Game

题目大意

给定一张 n\times m 的矩形网格纸，双方轮流操作，谁先剪出 1\times 1 的方格获胜。问先手是否有必胜策略。

思路

因为 \texttt{SG} 函数解决的是 不能走就输 的问题，所以对于 走到某个位置赢 的问题是不能直接解决的。因此，我们需要进行转化。经典做法是往前推直到推出必败态作为有向图游戏的终点。

这道题的必败态就是 (2,2),(2,3),(3,2)，因为当先手面对这三个局面时，就是必败状态。

但是必败态有时候并不好找，还有一种处理方法是，如果下一步的状态是必胜态，则下一步不能走。对于这道题，必胜态就是 (1,n) 或 (n,1)，即不能给对手剪出 (1,n) 或 (n,1) 的方格。

int dfs(int n, int m) {
    if (f[n][m] != -1) return f[n][m];
    vector<int> vec;
    _for(i, 2, n - 2) vec.push_back(dfs(i, m) ^ dfs(n - i, m));
    _for(i, 2, m - 2) vec.push_back(dfs(n, i) ^ dfs(n, m - i));
    return f[n][m] = mex(vec);
}