专栏指路《再来一遍一定记住的算法那些你可能忘记了的算法》前导博弈论Game Theory是研究具有斗争或竞争性质现象的数学理论和方法也是运筹学的一个重要分支。在信竞中我们不需要对此了解太深只要看懂原理证明后熟记模板。1.巴什博奕Bash Game规则有一堆物品共个两个玩家轮流取物每次可以取个最后取光物品的人获胜必胜策略若则先手必败否则先手必胜原理解析当物品数量是的倍数时无论先手取多少后手都可以取先手取的数量使剩余物品数仍是的倍数。最终会剩下个物品先手无论取多少后手都能取光获胜。示例先手必胜先手先取个使剩余个的倍数之后无论对手取个先手都取个最终先手获胜代码先手获胜输出 1后手获胜输出 2#includebits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, K; cin n K; if (n % (K 1) ! 0) { cout 1 \n; } else { cout 2 \n; } return 0; }至此我们初步了解博弈的规则想尽办法让对手处于必败之地。在巴什博弈中当前玩家的物品数满足就是必败的。因为无论怎么取对方玩家都能让你回到必败状态。而最小的必败状态为最终游戏失败。2.尼姆博弈Nim Game规则有多堆物品数量分别为两个玩家轮流从某一堆中取任意多的物品最后取光所有物品的人获胜必胜策略计算所有堆物品数量的异或值异或把运算的两个数转成二进制相同位为反之为若则当前局面为必败态先手必败若则当前局面为必胜态先手必胜原理解析尼姆和异或值为的状态称为必败态P-position尼姆和不为的状态称为必胜态N-position而我们需要证明1必胜态的后续操作里必有一个必败态2除外的必败态的后续操作都是必胜态3必败态和必胜态交替出现物品不断变少终态为必败态证明1如果我们拿到必胜态异或值设的二进制为的最高位为。我们只要找中二进制为的最高位也是的易证必定存在这样的且必为奇数个让异或上此时的第位变成整体变小符合操作规范。全部的异或值变成为必败态。证明2如果我们拿到必败态异或值因为不是。所以中肯定存在二进制第位为的数且为偶数个。只要让这些二进制第位为的其中一个的第位变成整体异或值就不为。就是你无论怎么取都会脱离必败态而且操作后的一定不为证明3在保证双方都是最优策略的情况下两态肯定是交替出现。且每个都不断减小最终为是必败态。例题指路P2197 【模板】Nim 游戏 - 洛谷 (luogu.com.cn)代码#includebits/stdc.h using namespace std; int main () { ios::sync_with_stdio(false); cin.tie(0); int T; cin T; while (T--) { int n; cin n; int sum 0; for (int i 1; i n; i) { int x; cin x; sum ^ x; } if (sum 0) { cout No \n; } else { cout Yes \n; } } return 0; }通过进一步的了解我们发现应该让对手的下一次操作也就是轮到我们时是必胜的。接下来的学习我们会通过这些总结的规律来给不同的情况建立尼姆博弈模型。2.1.输出方案的尼姆游戏/取火柴例题P1247 取火柴游戏 - 洛谷 (luogu.com.cn)这道题要求我们在先手必胜的情况下输出先手的取物方案。根据前面的分析我们知道要找中二进制为的最高位也为二进制为的最高位的。同时题目要求字典序最小for 一遍就好。代码#includebits/stdc.h using namespace std; const int N 5e5 10; int a[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; int sum 0; for (int i 1; i n; i) { cin a[i]; sum ^ a[i]; } if (sum 0) { cout lose \n; } else { for (int i 1; i n; i) { if ((a[i] ^ sum) a[i]) { //如果异或上 S 的 a[i] 变小了那么就说明这个 a[i] 第 k 位为 1 //如果 a[i] 第 k 位为 0异或上 S 第 k 位肯定会变成 1就变大了 //虽然这里不加括号优先级顺序也是对的但还是保险起见 cout a[i] - (a[i] ^ sum) i \n; //注意是先输出拿了多少个然后再 i a[i] (a[i] ^ sum); //a[i] 变成取完的样子 break; } } for (int i 1; i n; i) { //再输出一遍 cout a[i] ; } cout \n; } return 0; }2.2.尼姆游戏变形/反转硬币题面在一条直线上排列着一行硬币有的正面朝上、有的背面朝上。2 名游戏者轮流对硬币进行翻转。翻转时先选一枚正面朝上的硬币翻转。如果愿意可以从这枚硬币的左边选取一枚硬币一同翻转左边的硬币不一定要正面朝上。最后翻转使所有硬币反面朝上的玩家胜利。输入给你初始状态正面朝上硬币的集合。解析假设初始状态第 x 个硬币是正面朝上的如果翻动 x有以下几种情况1不翻左边的那么在正面朝上硬币的集合里x 就会直接消失。2翻左边的左边的硬币反面朝上那么在正面朝上硬币的集合里x 会变成被翻的左边硬币的下标。3翻左边的左边的硬币正面朝上那么在正面朝上硬币的集合里x 和左边的硬币下标会一起消失。注意到前面两种情况很像尼姆游戏1是把大小为 x 的物品堆全部取完。2则是从大小为 x 的堆里取出 x -左边硬币的下标个。3可以理解为同样从大小为 x 的堆里取出 x -左边硬币的下标个而在初始堆个数集合正面朝上硬币的集合里x 变成了左边硬币的下标。发现现在的x 和左边硬币下标相同两者异或值为 0。也就是相当于不对尼姆和做出贡献相当于在正面朝上硬币的集合里x 和左边的硬币下标一起消失。代码就不放了就是尼姆博弈的板子。2.3.*必学台阶型尼姆游戏Staircase Nim题面游戏开始时有许多硬币任意分布在楼梯上共阶楼梯从地面由下向上编号为到。每次操作时可以将楼梯上的若干个至少一个硬币移动到楼梯上。两名游戏者轮流操作将最后一枚硬币移至地上的人获胜。解析这次我们来尝试自己发现必胜策略。考虑所有台阶只有一个台阶上有一个硬币的情况易得如果这个硬币在奇数台阶上先手必胜。如果这个硬币在偶数台阶上先手必败。第阶台阶是地面这可以同化到普通尼姆游戏的“所有堆只有一个堆有硬币”的情况。于是我们猜测台阶型尼姆游戏的必胜策略为当奇数台阶上硬币数的异或和不等于 0时先手必胜。反之必败。该如何证明呢还记得前面的三条定律吗1必胜态的后续操作里必有一个必败态2除外的必败态的后续操作都是必胜态3必败态和必胜态交替出现物品不断变少终态为必败态只要证明我们猜测的必胜策略满足上面三条那么该策略就是正确的。读者自证不难这里就不赘述了好吧我还是讲讲。大家可以把偶数级台阶看作丢硬币的框子把奇数台阶看作普通尼姆游戏的硬币堆。和之前证明唯一的不同点就是是可以变大的。如果遇到了奇数台阶全为的情况但还有偶数台阶不为 0。那这时候无论怎么做都会让一个奇数台阶变大就相当于增加。而之后的操作虽然会增加有些但最后所有硬币都会流向更低的台阶也就是地面可以证明所有硬币流向地面一定是经过偶数次操作。这时轮到的人是遇到奇数台阶全为的情况的人游戏失败。所以奇数台阶全为的情况是必败态。总结对于上一个物品堆的数量可以传递到下一个的博弈是阶梯尼姆博弈。做这类题的时候要注意哪类变量可以相邻传递判别哪些是无关紧要的“偶数阶梯”。例题原题[POJ1704] Georgia and Bobacwing 链接236. 格鲁吉亚和鲍勃 - AcWing题库解析注意到选择一个棋子并将其向左移动但是不能越过任何其他西洋棋棋子或超过左边界。也就是当前棋子 i 的移动范围只有i 的前面至棋子 i - 1 的后面。当 i 往前移动i 1 的移动范围增加 1。而所有棋子移动范围归 0 时为必败态终态。那台阶尼姆模型就已经很明显了我们把1 格到第 1 个棋子间的空白格第 1 个棋子的可移动范围作为 a[n]。第 1 个棋子和第 2 个棋子间的空格第 2 个棋子的可移动范围作为 a[n - 1]以此类推第 n - 1 个棋子和第 n 个棋子间的空格第 n 个棋子的可移动范围作为 a[1]。因为台阶模型的模板就是 a[i 1] 传递到 a[i]所以这里这样定义还有一个比较阴的就是输入的位置不是从小到大需要自己排。代码#includebits/stdc.h using namespace std; const int N 1e3 10; int a[N], p[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int T; cin T; while (T--) { int n; cin n; for (int i 1; i n; i) { cin p[i]; } sort (p 1, p n 1); int sum 0, last 0; // 假如第 1 个棋子在 2 格那么它的可移动范围就等于 2 - 0 - 1 for (int i 1; i n; i) { a[n - i 1] p[i] - last - 1; // 假如上一个棋子在 3 格当前棋子在 5 格那么可移动范围就是 5 - 3 - 1 last p[i]; } for (int i 1; i n; i) if (i 1) { sum ^ a[i]; } if (sum ! 0) { cout Georgia will win \n; } else { cout Bob will win \n; } } return 0; }2.4.多堆限制型尼姆游戏Moores Nim_k规则n 堆石子每次可以从不超过 k 堆中取任意多个石子最后不能取的人失败。判断把 n 堆石子的石子数用二进制表示统计每个二进制位上 1 的个数。若每个二进制位上 1 的个数全部为 0则先手必败否则先手必胜。解析我们发现这和之前讲过的巴什博弈有点像其实两者本质原理是一样的。如果当前为必败态非终态这轮的玩家取完。下一轮的玩家只要遍历所有二进制位如果当前二进制位有堆被取过那当前玩家就取该位为的 1 的堆直到该二进制位 1 的个数为 0。2.5.反尼姆游戏anti-nim规则有多堆物品数量分别为两个玩家轮流从某一堆中取任意多的物品最后取光所有物品的人失败。判断一个状态为必胜态当且仅当1所有堆的石子个数为 1且尼姆和为 0。2至少有一堆的石子个数大于 1且尼姆和不为 0。解析顾名思义就是取光物品反而失败的尼姆游戏。那判断条件为什么不是普通尼姆游戏反着来呢我们看单堆的情况在普通尼姆游戏数量不为 0 的单堆是必胜态。但在反尼姆游戏中单堆且数量为 1 才是必败态。这是因为两者遵循不同的取胜技巧在普通尼姆中当只剩一堆石子时玩家会取走所有石子获胜在反尼姆中当只剩一堆且 1 个石子时玩家会留下 1 个石子迫使对手失败所以我们应该以一个新的视角去看待反尼姆。分类讨论下1所有堆的石子个数为 1有奇数堆很明显这是必败态。2所有堆的石子个数为 1有偶数堆这是必胜态。3其他情况经过2.4的思考你应该稍微有点头绪假设上一个玩家面对的状态是每个二进制位上 1 的个数都是 2 的倍数当前玩家只要遍历上一个玩家取过堆的所有二进制位如果该二进制位被改变了那就去找其他这个位为 1 的堆 把那个堆的 1 取出来就行。所以上一个玩家是必败态。更归纳的想如果每个二进制位上 1 的个数都是 2 的倍数那么当前状态的尼姆和就为 0反之不为 0。也就是尼姆和为 0 的是先手必败态反之为必胜态。意外的和普通尼姆的判断方式一样呢例题P4279 [SHOI2008] 小约翰的游戏 - 洛谷 (luogu.com.cn)代码很板的反尼姆按照判断部分打就行。#includebits/stdc.h using namespace std; const int N 510; int a[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int T; cin T; while (T--) { int n; cin n; int sum 0; bool flag 0; for (int i 1; i n; i) { cin a[i]; if (a[i] ! 1) { flag 1; } sum ^ a[i]; } if (flag 0) { if (n 1) { cout Brother \n; } else { cout John \n; } continue; } if (sum ! 0) { cout John \n; } else { cout Brother \n; } } return 0; }2.6.*必学树上阶梯尼姆/初见SG 函数很抱歉我没有把这道题放在2.3后面但我觉得按难度排的话这样是最好的。例题P2972 [USACO10HOL] Rocks and Trees G - 洛谷 (luogu.com.cn)哎洛谷这糟糕透顶的题面别看。看我的首先再来回顾下我们的两种状态。在任何回合制游戏中在双方都绝对聪明最优解一个局面只有两种命运必败态P-position轮到你走但你不管怎么走都会把“胜利”拱手送给对方。必胜态N-position轮到你走你至少有一种走法能把“必败”扔给对方。判断规则很简单没有可走游戏结束状态→必败。如果所有走法都会走到“必胜态” → 当前是必败因为你无论怎么走都会把“必胜”送给对方那你不是输定了吗如果存在一种走法能走到“必败态” → 当前是必胜因为你可以故意走那一步把“必败”扔给对方让对方头疼去。至此我们再次总结博弈论的底层逻辑尽量把烂摊子留给对方。2.6.1.介绍SG 函数和mex一个游戏局面如果轮到某人操作不能操作的局面的 SG 值 0。一个局面的 SG 值 它所有“走一步之后”的局面的 SG 值中没有出现过的最小非负整数。这个操作叫 mex最小排除值。定义当前状态 SG 函数如果为 0则必败不为 0 则必胜。如果局面能一步走到 SG0必败那mex不会选 0它至少会选 1。 SG 0 →必胜。如果局面所有走法都去不了 SG0那mex就只能选 0。所以 SG 0 →必败。所以SG 值是否为 0直接对应“必胜 / 必败”。我们发现这里的SG 函数的定义就是前面所说的尼姆和只不过我们换了种方式证明。同时SG 函数和 mex的运用范围也更广任何满足双人轮流、零和只分输赢不和局、游戏过程透明、无随机性、有限性一定会结束即所谓“公平组合游戏”。的游戏都可以使用 SG 函数来判断胜负态。2.6.2.重新理解异或当游戏被劈成好几段分成小游戏时它们互不干扰轮流操作时你一次只能动其中一段。就相当于尼姆游戏一次只能取一个堆本题一次只能移动一个点的石子。这时候不能直接把 SG 值加起来比如 11 2考虑使用异或XOR。因为异或有一个神奇的性质它完美符合“必胜/必败”的传递规则如果一堆数字的异或结果是 0那么你只要改变其中一个数字把它变小或变任意数异或结果一定不是 0。如果异或结果不是 0那么你总能找到一种方法只改变其中一个数字让新的异或结果变成 0。这完全对应了第一步里的“必胜/必败”规则总异或 0必败无论你怎么操作相当于改变其中一个 SG 值结果必然非 0走到必胜态。总异或 ≠ 0必胜你一定有办法把它变成 0走到必败态。解析说回本题是个很明显的阶梯尼姆只要异或上树奇数层的点的 SG 值就能判断答案。从根节点 10层开始一层层往下层数递增考虑求出每个点的 SG 值。注意到“最多 L 个石头从这个节点向树根靠近一个单位。”那么对于石头数量的点。都可以达到只有本身不行对于石头数量的点。对于石头数量的点。以此类推得换个脑子想这不就是巴什博弈嘛。代码#includebits/stdc.h using namespace std; const int N 1e4 10; int sg[N], p[N], r[N], dep[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int n, T, L; cin n T L; for (int i 1; i 1000; i) { sg[i] i % (L 1); } int sum 0; dep[1] 0; for (int i 2; i n; i) { cin p[i] r[i]; dep[i] dep[p[i]] 1; if (dep[i] 1) { sum ^ sg[r[i]]; } } for (int i 1; i T; i) { int x, y; cin x y; if (dep[x] 1) { //不是奇数层对异或值没影响 sum ^ sg[r[x]]; // 再异或上一次就相当于没异或 r[x] y; sum ^ sg[r[x]]; } if (sum ! 0) { cout Yes \n; } else { cout No \n; } } return 0; }2.7.有向无环图的尼姆游戏/再会 SG 函数题面来源USACO 2006 January Gold样例输入42 1 201 301 02 0 2041 11 2002 0 12 1 13 0 1 30样例输出WINWINWINLOSEWIN解析拓扑好序列按照拓扑序列从后往前没有后继的点的 SG 值为 0必败有后继节点的点就用mex 函数。最后的总状态为所有点的SG 值的和异或和。我觉得不太难代码写了注释直接看就好代码#includebits/stdc.h using namespace std; const int N 1010; int sg[N], n; vectorint G[N]; int dfs_SG(int x) { if (sg[x] ! -1) { //记忆化搜索 return sg[x]; } bool v[1010] {0}; //一定要在里面定义 for (int y: G[x]) { v[dfs_SG(y)] 1; // mex{SG[y]} } int i 0; while (v[i]) { // 从 0 开始找第一个没出现过的 SG i; } return sg[x] i; } int main() { ios::sync_with_stdio(false); cin.tie(0); while(cin n) { memset(sg, -1, sizeof(sg)); for (int i 0; i n; i) { int x; cin x; G[i].clear(); //多测要清空 for (int j 1; j x; j) { int y; cin y; G[i].push_back(y); // 建图 } } int m; while (cin m) { if (m 0) { break; } int sum 0; for (int i 1; i m; i) { int x; cin x; sum ^ dfs_SG(x); } if (sum ! 0) { cout WIN \n; } else { cout LOSE \n; } } } return 0; }2.8.要求从集合中选数的尼姆游戏题面POJ 2960 S-Nim代码实在是太简单了我真的不想写解析。其实这个做法的复杂度存疑不过现在机子跑得快过这道题绰绰有余#includebits/stdc.h using namespace std; const int M 1e5 10, N 110; bool v[M]; int sg[M], k[N], sum[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int K; while (cin K) { if (K 0) { break; } for (int i 1; i K; i ) { cin k[i]; } memset(sg, 0, sizeof(sg)); memset(v, 0, sizeof(v)); for (int i 1; i M - 10; i) { for (int j 1; j K; j ) if (k[j] i) { v[sg[i - k[j]]] 1; } for (int j 0; j M - 10; j ) if (!v[j]) { sg[i] j; break; } for (int j 1; j K; j ) if (k[j] i) { v[sg[i - k[j]]] 0; } } int T; cin T; for (int i 1; i T; i) { int n; cin n; sum[i] 0; for (int j 1; j n; j) { int x; cin x; sum[i] ^ sg[x]; } } for (int i 1; i T; i) { if (sum[i] ! 0) { cout W; } else { cout L; } } cout \n; } return 0; }3. 威佐夫博弈 (Wythoffs Game)规则有两堆物品数量分别为和两个玩家轮流操作每次可以从一堆中取任意多的物品从两堆中取同样多的物品最后取光物品的人获胜必胜策略令计算计算其中黄金分割比若则当前局面是必败态否则是必胜态性质威佐夫博弈的必败态为其中必败态满足完备覆盖性每个正整数恰好出现在一个必败态中这满足定律1必胜态的后续操作里必有一个必败态。无重复性任意两个必败态没有公共元素这满足定律2除外的必败态的后续操作都是必胜态而前面两条和威佐夫博弈的定义恰好满足定律3必败态和必胜态交替出现物品不断变少终态为必败态证明beatty 定理如果一对无理数和满足那么这样两个数列 :其实就是和的并集啦就既无重复又无遗漏地包含了所有的正整数。证明指路。我们发现将代入和代入正好满足。也就是威佐夫博弈的必败态为其中满足三定律。例题P3024 [USACO11OPEN] Cow Checkers S - 洛谷 (luogu.com.cn)代码板令当时为必败态。#includebits/stdc.h using namespace std; int main () { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; int T; cin T; for (int i 1; i T; i ) { int x, y; cin x y; if (x y) { swap(x, y); } double t 1.0 * (y - x) * (1 sqrt(5)) / 2; if (x floor(t)) { cout Farmer John \n; } else { cout Bessie \n; } } return 0; }