学习来源：[学习笔记] （博弈论）Nim游戏和SG函数_nim博弈-CSDN博客
后面二、三有完全转载情况，主要是迫不及待去刷题了。
mex：获取不属于该集合的最小非负整数。
例如：mex{} = 0（空集合）mex{0，1，2，4} = 3； mex{2，4} = 0；
没有0的集合mex函数值为 0， 有0的集合mex函数值为非0.
有向无环图：x为当前局面也就是顶点。 y为x的后继也就是x指向y顶点，y也就是x的下一个局面。
sg(x) = mex{sg(y)| y为x的后继）,要想建立sg函数，就需要知道sg的最深层sg值，也就是最后一个无后继顶点。
一堆石头，有n个，每次可以的数集合{1，3，4}即step[] = {1,3,4}, 求其sg值？
首先，sg[0] = 0; 也是游戏终点顶点x = 0处。
因为sg(x) = mex{sg(y) | y是x的后继） 想要建立sg函数，首先求出sg(1),从0递推到n。这是sg函数的递归关系，也就有向无环图的前驱后继关系，x是前驱，y是后继。
把原游戏分解成多个独立的子游戏，则原函数sg函数是所有子游戏的sg函数值的异或
sg(G) = sg(G1)^sg(G2)^……^sg(Gn).
分别考虑每一个子游戏，计算其sg值
（1）可选步数step集合1-m连续整数，直接取模SG(x) = x%(m+1)
（2）可选步数step集合任意步数， SG(x) = x
（3）可选一系列不连续，用模板计算，上面那个表格，下面是代码打表和dfs建立sg
核心是搜索遍历
①打表
核心思想：
总结：sg(x) = mex{sg(y)| y是x的后继}： 也就是满足递推关系，从最底层顶点可以递推出sg(x),最底层sg[0] = 0;
（1）从1 -> x 每一个局面遍历
（2）标记每一个局面的子局面sg函数值
（3）获取每一个局面的当前局面sg函数值：遍历：未标记的sg值，（不属于子局面的sg值最小非负整数）
代码
step 的排序是防止在遍历每一种子局面时出现局面遗漏
for(int j = 1; step[j] <= i; j ++) 如果，step = { 1，5，3} 而i 只搜索到 4，则step只能时{1} 本应该是{1，4} 两个进入子局面的选择。
②dfs
核心思想
总结：搜索当前局面的每一种子局面可能，sg(x) = mex{sg(y)| y是x的后继}
（1）递归出口x = 0；sg[0] = 0；
（2）遍历搜索每一种可能step可能选择，进入dfs进入子局面
（2）标记当前局面的子局面sg（y)值
（4）获取：当前局面sg（x)函数值搜索未标记也就是非子局面的最小sg值
代码
sg初始化为-1.不为-1，说明搜索到了sg[0]=0；0之后不会再有局面了，也就是游戏结束了。
sg[] 为x 对应的sg函数值，在所有堆中也是一样的
今天我们要认识一对新朋友，Alice与Bob。
Alice与Bob总是在进行各种各样的比试，今天他们在玩一个取石子的游戏。
在这个游戏中，Alice和Bob放置了N堆不同的石子，编号1..N，第i堆中有Ai个石子。
每一次行动，Alice和Bob可以选择从一堆石子中取出任意数量的石子。至少取1颗，至多取出这一堆剩下的所有石子。
假设每一轮游戏都是Alice先行动，请你判断在给定的情况下，如果双方都足够聪明，谁会获得胜利？
Nim游戏是经典的公平组合游戏(ICG)，
对于ICG游戏我们有如下定义： 根据某种操作规则，使一方无法移动进入下一个局面。
- 两名选手
- 两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个
- 游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它因素；局面的改变称为“移动”(move)
- 如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负
对于第三条，我们有更进一步的定义Position，我们将Position分为两类：
- P-position：在当前的局面下，先手必败
- N-position：在当前的局面下，先手必胜
它们有如下性质：
- 合法操作集合为空的局面是P-position
- 可以移动到P-position的局面是N-position
- 所有移动都只能到N-position的局面是P-position
算法实现
取子游戏算法实现——
步骤1:将所有终结位置标记为必败点（P点）；
步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）
步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ；
步骤4: 如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。
当然，我们这里会讲这个题目就说明肯定没那么复杂。没错，对于这个游戏有一个非常神奇的结论：
对于一个局面，当且仅当A1 xor A2 xor … xor AN =0时，该局面为P局面。
如何证明这个结论呢？
分类讨论一下。
如果当前局面上的所有棋子都不能走了，显然它们的sg函数值都是零，那么先手必输。
那普通局面就相当于有sg函数的值不为零。
还是分类讨论。
如果现在对手走，sg值异或和为零（注意是异或和），他会选一个石子，然后把这个石子放到它的孩子结点上。sg值有可能增加，也有可能减少。只要sg值增加，你就把它还原回来（根据sg函数的定义，好好思考一下！），那么sg函数总有不能增加的一天，因为第一条的引理。这就相当于sg值只能减少！那这不是一个nim游戏吗？根据nim游戏里面的证明，你一定可以找到一个数，找一个石子堆，减去这个数以后，异或和还是零。最终对手就会被逼迫到第二条的局面上，然后它就输了。反之如果异或和不为零，你一定输！
到此这篇莫队算法的由来（莫队算法是谁发明的）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/bcyy/65884.html