博弈论：公平组合游戏（Nim游戏&SG定理）学习笔记公平组合游戏定义：两人轮流以最优方式操作，两人的操作方式相同。每次操作游戏状态必须改变，不能操作者输，另一人赢。每个游戏状态不能重复到达。我们把每个状态看作一个点，每个状态的点向它后继状态的点连有向边，可以生成一张DAG（

发现大多数的题解都是不同于官方题解的做法，这里我将介绍官方题解做法。Solution证明先手是否可以必胜的方法相差无几，为了方便后边行文，这里介绍我的思路：考虑各堆石子和为奇数的情况（以下简称为“奇状态”，另一种称为“偶状态”）一定先手必胜：两人一次取一个即可。考虑偶状态。可以发

荷马史诗Huffmantree板子。CF474FAntcolony维护区间gcd，min，min数量sum。输出\(r-l+1-[gcd=min]sum\)。AGC033CRemovingCoins每次相当于找\(u\)满足最远的点距离为奇数，然后删掉所有叶子。删完之后会剩下1/2个点，判断点的最远边的奇偶即可。假了考虑一次操作的

考虑到两人对应的操作是相同的，于是可以从对称的角度来思考。考虑到在先手做出操作后，后手一个较为特殊的操作是不做任何影响，也就是重复先手的操作。能够发现如果对于后手这不能必胜，那么他一定不会去产生影响，并又把这个局面留给先手，相当于是先后手的交换。对于先手又是同样的，因为

A.防诈骗\(\text{Sol1：}\)首先可以把这\(n\)个水杯划分为不交的链，对链暴力\(\mathrm{mex}\)之后发现很有规律，按照经典结论把所有游戏的\(SG\)函数求异或和，如果为\(0\)那么后手必胜，否则必败。但是由于是求第\(k\)小满足后手必胜的\(n\)，所以只能拿答案\(\le10^7\)的

定义必胜或必胜状态：仅仅考虑当前的状态，不考虑的操作人时，一定必胜或必输\(a\oplusb\)：\(a,b\)在二进制下，对位取反。Nim游戏考虑有\(n\)堆石子，两个人轮流来拿走棋子（至少拿一个），拿到最后剩下的一颗棋子的人获胜。结论：定义Nim和\(=a_1\oplusa_2\oplusa_3\oplus\dots

T1新的阶乘（factorial）线性筛出质数和每个数的最小质因数，然后直接算即可。T2博弈树（tree）结论：当且仅当起点为直径中心时，后手必胜。证明：先考虑只在直径上的博弈，如果起点在直径的一端，先手必胜，设直径长为\(len\)，如果在端点的下一个位置，先手可以移动\(len-2\)到对称位置，此时后手

如果尝试去刻画这个问题，会发现非常复杂，于是不妨一步一步来。考虑Alice的第一步，此时Alice操作的位置是固定的。考虑把\(a_n\)移到一个位置后，接下来的\(\max\)是\(a_{n-1}\)或\(a_n\)，Bob对应也只能这么操作。注意到Bob也有可能操作的是\(a_n\)，这看起来就很特殊

SG函数是用于解决博弈论中公平组合游戏（ICG）问题的一种方法ICG这是啥？定义大概就几条：双方参与，轮流决策，决策最优无法决策时游戏结束，无法决策者输，不论如何决策游戏都能在有限步完成同一状态不可多次抵达，游戏无平局，任意决策者在决策点的行为与决策者无关仅与决策点有关这就是I

P6803星际迷航题解题目大意给定一颗\(N\)个节点的树。这样的树有\(D+1\)层，编号从\(0\)到\(D\)。对于\(i=0,1,\dots,D-1\)，需要选择第\(i\)层的任意一个节点向第\(i+1\)层的任意一个节点连一条有向边。最初人在第\(0\)层图的\(1\)号节点。两个玩家交替选择下一

思路这道题需要倒序计算。定义$dp_{i,j}=f$表示第$i$轮结束后余数为$j$，$f=1$时，Takahashi必胜，否则Aoki必胜。动态转移方程式令：$x=dp_{i,(j\times10+a_i)\bmod7}$$y=dp_{i,j\times10\bmod7}$$dp_{i-1,j}=\begin{cases}x\\operatorname{or}\y&b_i=T\x\

首先考虑最简单的情况，如果有一个数是\(1\)，那么第二步没有作用，胜负是固定的，先判掉。然后发现题目给了一个很奇怪的条件：所有数的最大公约数为\(1\)，也就是至少有一个奇数，这提示我们从奇偶数下手。发现第二步中的最大公约数的奇数因子是毫无意义的，因为无论是奇数还是偶数除以一个

文章目录写在前面公平游戏写在前面听说CSDN给米就来了，不过作为一个品质优良的程序员来说，无私奉献是我应该做的，所以博主写的文章基本上不花钱，都是为了以后某天忘记了，自己能看懂才写的。so，我会写的很啰嗦，直到保证忘记的我能够看懂。对于读者嘛，能看就看吧，我就不管了。

Nim经典的博弈论大致意思：地上有n堆石子，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。问是否存在先手必胜的策略。乍一看手玩一下，发现很复杂，于是考虑把游戏状态形式化地表示出来便于观察。设先手为a，后手

1.Nim博弈结论先手必胜当且仅当\(\oplusSG(A_i)\not=0\)。2.Nim-K博弈每次可以选不超过\(k\)堆石子，Nim可以看成\(k=1\)的情况。结论先手必败当且仅当每个二进制位上满足\(1\)的个数是\(k+1\)的倍数。proof3.Multi-SG在符合拓扑原则的前提下，一个单一游

简单博弈题。先说结论，如果存在\(a_i=0\)使得\(1\lei\lea_1\)的话，那么先手必胜，否则后手必胜。若满足上述条件显然先手必胜，将\(0\)搞到第一个就行。否则Alice每操作一次，如果操作后满足了上述条件，那么Bob赢，否则Bob只要不动就行。但是下一轮Alice必须动，要不然两

arc131C考虑奇数情况，只有一个时先手必胜，设当前异或和为\(S\)，必输的情况是\(\forallS\oplusa_i\ina\)，这些数是一一对应的，但一共有奇数，此时先手必胜。偶数是，若第一回合无法结束游戏则变为后手，同上。E若一个点所有边颜色相同，包含该点的环便不可能三边颜色不同，转化为对

题目链接：hdu7548SunBian(2024“钉耙编程”中国大学生算法设计超级联赛（10）)思路：一道比较签到的题。先说结论：1.当n=k时A必胜2.当k=1时，n为奇数A胜，否则B胜3.其余情况全都为B胜证明：1.显然n=k时A可以一回合全部取完2.k=1时双方只能轮流来，显然奇数A胜偶数B胜3.此时A是

正在完善！何为博弈论博弈论，是经济学的一个分支，主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。先来看一道小学就接触过的思维题你和好基友在玩一个取石子游戏。面前有30颗石子，每次只能取一颗

没打，在军训a:我们可以利用操作来实现AA...AAB和ABB...BB这样的近似回文串的东西。如果有一个B那么这样的字符串就是可行的。设回文串为S。SBAA...AABS和SAB...BBBAS所以搞一个头尾，然后如果左边是B或右边是A那么就可以，否则判下左右是否相等，然后继续下去。然后有个代码小细节

博弈论学习笔记一.公平组合游戏（ImpartialGame）公平组合游戏满足以下性质：决策公平（双方操作的集合是一样的）无隐藏信息（双方均知道游戏的所有信息）无随机部分无平局有固定的结论是，若双方都绝顶聪明，对于固定的状态\(G\)，能判断其是必胜还是必败态。二.巴什博弈（BushGame）只有

SunBian显然，有如下的两种特殊情况：\(k=1\)，此时每人只能操作一个，那么显然为奇数Alice必胜，为偶数Bob必胜；\(k=n\)，此时Alice一次可以全部操作，那么Alice必胜。除此之外，Alice无论第一步如何操作，Bob都有一种方式，使剩下未操作的分成两个一样长的连续段（长度可以为），根据

题目链接：HDU3590【PPandQQ】思路    树上删边问题，套个反尼姆博弈。    反尼姆博弈是取走最后一个石子的人输掉游戏，所以需要特判一些特殊情况。    1.有堆的石子个数都是1，所以堆数为奇数时，先手必败，否则先手必胜    2.所有堆中存在石子数为

手玩题思路由于数据范围小，所以可以手动模拟找规律。假设\(A\)为先手，据题意，当轮到\(A\)操作时，如果此时序列里最大数为\(0\)（也就是序列里全是\(0\)），那么\(A\)就赢了。由于\(A\)操作时序列的状态是由\(B\)操作时的序列取模之后得到的，所以\(B\)操作时的序列中的元素肯定有相同的约

bash:一堆石子共n个，两人轮流从中取石子，规定每次至少取一个，最多取m个，最后取光者得胜。问两人博弈，他们都采用最聪明的策略，问最后谁可以必胜。首先我们从小开始分析：当m>=n时，先手可以一把抓完石子，这样先手必胜当n=m+1时，先手无论怎么抓，都会留下1~m个石子，这样后手一把就可以抓完，这样