博弈 SG函数
为什么要学习这个呢？因为每次看到题解的第一句话总是这种的：
水题，简单题，模板题，打表题
然后，第二句话，就是结论，比如sg【x】等于（然后一个分类），就得到了公式
最后就是把所有的亦或起来，就得到了答案了
首先呢，可以把这个题做一做，是一个很好的博弈题。题目链接：HDOJ5754
这个题，解释了博弈的很经典一个思路：找平衡
什么叫做平衡？就是当博弈的局面达到了对称的时候，后手总是可以模仿先手的操作，从而让先手失败
而先手要是想要获胜，那么第一步必须建立对称局面
博弈中的另外一个很重要的思路是P局面和N局面，官方定义和解释如下：
（1）无法进行任何移动的局面是P局面
（2）可移动到P局面的局面是N局面
（3）所有操作都导致N局面的局面是P局面
P局面就是常说的必败态，N局面就是常说的必胜态
也就是说：必败态就是无路可走，或者下一步状态都是必胜态
必胜态的下一步状态至少有一个是必败态
现在来定义SG函数，函数g（x）=mex【g（y）】，其中y是x的后继
mex是一种运算，表示的含义是：最小的不属于这个集合的非负整数
例如mex【0,1,2,4】=3，mex【】=0，mex【2,3,5】=0
这就给我们打表提供了理论依据，如何判断一个状态x的结果，只需要根据mex函数，去求他的所有子状态y的结果
相信其他的博客有更好的理论解释
我这里提供几个打表的例题，打表的过程和原理会详细解释
因为博弈的状态转移关系是不定的，需要根据输入动态调整
原理是要求sg（x），先得算出所有的sg（y），所以用记忆化搜索
sg（x）的函数值，是mex【sg（y）】，所以把sg（y）放到mex数组中，然后从前往后找，找到第一个mex【i】=0的i值，即有sg（x）=i
状态转移分为两种情况，把一堆分成3堆，或者是把一堆取走任意个石子（不能不取），就是对于sg【x】，x的所有后继y怎么来
会了5795之后，这个题应该是改改就出来了吧
题中给定的转移数目是Fibonnaci数，需要提前计算有多少个可能值
在转移的时候，一定要记得选择拿走的Fibonnaci数不能超过当前的x
贴了几个题之后，总结下方法吧：
1：自己先手算几个结果，方便理解题意，方便打表
2：考虑可能的所有转移情况，根据SG函数的原理来打表
3：如果能够找到规律，那么直接用规律做
4：如果看不出规律，那么采取记忆化搜索的方式
5：总之，nim和SG函数都是比较套路的题，需要好好研究，比赛的时候是需要弄出来的题
SG函数和NIM游戏中较难的变形题
小米集团公司福利 444人发布
投递旷视等公司10个岗位 >
