威佐夫博弈
有两堆石子，给出每一堆的石子数量，两名玩家轮流行动，每人每次任选以下规定的一种操作石子：
- 任选一堆，取走正整数颗石子；
- 从两队中同时取走正整数颗石子。
拿到最后一颗石子的一方获胜。双方均采用最优策略，询问谁会获胜。
以下局面先手必败：
\(\pmb{ (1, 2), (3, 5), (4, 7), (6, 10), …}\) 具体而言，每一对的第一个数为此前没出现过的最小整数，第二个数为第一个数加上 \(\pmb{1,2,3,4,…}\) 。
更一般地，对于第 \(\pmb k\) 对数，第一个数为 \(\pmb {First_k= \left \lfloor \frac{k*(1+\sqrt 5)}{2} \right \rfloor}\) ，第二个数为 \(\pmb{Second_k=First_k+k}\) 。
其中，在两堆石子的数量均大于 \(10^9\) 次时，由于需要使用高精度计算，我们需要人为定义 \(\frac{1+\sqrt 5}{2}\) 的取值为 \(lorry = 1.618033988749894848204586834\) 。
const double lorry = (sqrt(5.0) + 1.0) / 2.0;
//const double lorry = 1.618033988749894848204586834;
void Solve() {int n, m; cin >> n >> m;if (n < m) swap(n, m);double x = n - m;if ((int)(lorry * x) == m) cout << "lose\n";else cout << "win\n";
}
斐波那契博弈
有一堆石子，数量为 \(N\) ，两名玩家轮流行动，按以下规则取石子：
先手第1次可以取任意多颗，但不能全部取完，此后每人取的石子数不能超过上个人的两倍，拿到最后一颗石子的一方获胜。
双方均采用最优策略，询问谁会获胜。
当且仅当 \(N\) 为斐波那契数时先手必败。
int fib[100] = {1, 2};
map<int, bool> mp;
void Force() {for (int i = 2; i <= 86; ++ i) fib[i] = fib[i - 1] + fib[i - 2];for (int i = 0; i <= 86; ++ i) mp[fib[i]] = 1;
}
void Solve() {int n; cin >> n;if (mp[n] == 1) cout << "lose\n";else cout << "win\n";
}
树上删边游戏
给出一棵 \(N\) 个节点的有根树，两名玩家轮流行动，按以下规则操作：
选择任意一棵子树并删除（即删去任意一条边，不与根相连的部分会同步被删去）；
删掉最后一棵子树的一方获胜（换句话说，删去根节点的一方失败）。双方均采用最优策略，询问谁会获胜。
结论：当根节点SG值非 \(1\) 时先手必胜。
相较于传统SG值的定义，本题的SG函数值定义为：
- 叶子节点的SG值为 \(\pmb 0\) 。
- 非叶子节点的SG值为其所有孩子节点SG值 \(\pmb + 1\) 的异或和。
auto dfs = [&](auto self, int x, int fa) -> int {int x = 0;for (auto y : ver[x]) {if (y == fa) continue;x ^= self(self, y, x);}return x + 1;
};
cout << (dfs(dfs, 1, 0) == 1 ? "Bob\n" : "Alice\n");
无向图删边游戏（Fusion Principle 定理）
给出一张 \(N\) 个节点的无向联通图，有一个点作为图的根，两名玩家轮流行动，按以下规则操作：
选择任意一条边删除，不与根相连的部分会同步被删去；
删掉最后一条边的一方获胜。双方均采用最优策略，询问谁会获胜。
- 对于奇环，我们将其缩成一个新点+一条新边；
- 对于偶环，我们将其缩成一个新点；
- 所有连接到原来环上的边全部与新点相连。
此时，本模型转化为“树上删边游戏”。