allblue
由于上次某人出的，应该说是借鉴的一道博弈论的题目，，感觉到自己的完全空白，，所以这次去网上看了好几篇文章，写下自己的心得体会
我看到网上很多人都是以nim的游戏开始介绍，然后讲SG值，mex函数，还有 Bouton's Theorem，都介绍的比较详细了吧
下面我来整理下
什么是nim游戏
首先根据以上的介绍，我们了解到ICG问题主要有以下几个个特点
1.当能到某人开始操作时，走不动了，这位选手就被判负，就是输了
2.必败的局面无法移动到必败局面
3.必胜的局面一定存在一种移法可以移动到必败的局面
以上的这三点在证明那个 bouton's theorem 时非常关键
我们再会过来看看nim游戏是怎么求解的，就是把n堆石子的个数异或处理，如果是0就是必败局面，非0就是必胜局面
这个结论十分优美，不是吗
初看之时实在是摸不清头脑
我们详细的看看
设有n堆石头，第i堆有ai个石头
首先在终点局面的时候一定是所有的石头都是扔完了的，那么就是0^0^0....^0=0
和我们前面说的那个特点相符合，终点的情况算出来是必败情况
接下来再看看是不是满足其余的两个特点
必败的局面无法移动到必败的局面
a1^a2^a3......an-1^an=0
显而易见，无论把其中的那个值移动后，一定得到的新的值不会是0
再看，必胜的局面一定可以移动到某个必败的局面
a1^a2^a3.....an-1^an=k
则一定可以讲某个ai->ai^k
则a1^a2..ai^k..^an=k^k=0
看上述的三个特都满足了
所以ICG的求解可以转换至求异或值
接下来我们看看SG值
在介绍SG值之前需要先说一下mex函数，改函数作用在集合之上
mex，表示不属于该集合的最小的非负整数
SG(x)=mex{ SG(y) | y是x的后继 }
就是求最小的一个非负的整数，不属于后继节点的SG值
我们一个游戏的进行过程看作是一张图
先看只有一个石堆的情况，它的所有移动情况构成了一副图
对于某个点而言，对应这游戏的某个局面
对于某个点的SG值来说，如果SG(x)=0，推出起所有的后继节点的SG值都非0
如果SG(x)!=0，推出其后继节点的一定存在某个后继节点的SG值为0
然后我们再来看最后一个节点，就是终点节点，因为没有后继节点了， 空集，所以就是0
怎么样是不是和那个游戏的规则灰常的像
但是这是对于1堆石子，事实上对与n堆石子而言，其结果就是
n个SG值的异或值，这个也就是游戏的和
也就可以把一个大游戏，分成n个子游戏来求解
再求n个游戏的和即可
下面我们来看几道题目
poj 2484
我们先简单的分析下这题
我们可以发现对于这个题目而言，n还是挺大的100w，无论你用dp还是什么都会太慢
状态数实在是太多了，不好描述
但是我们可以发现对于最终的状态，就是空而言，这一定是必败的状态
当还剩1个或者2个相邻的情况时，这是必胜的状态
2个分开的就是必败状态
如果我们能把石堆，通过操作分成2堆相同的，然后后手模仿先手的操作就可以保证后手必胜了
推出如果 SG(x)，x的状态如果是可以分成2堆完全相同的棋子，那么SG(x)=0
显然任何状态除了SG(x)=0的状态下都可以转向0，而且只能转向0
所以只要n大于等于2，就等于先手比必败了
poj 2348
这题呢，n，m两个值
首先我们可以假设n=m*k+b （0<=b<m , k>0）
假设n进行转移
可知，当n转移至m*s+b，s>1 时，并不会改变该选手的状态，因为后手的操作和先手的可操作状态并无实质性的改变
但是当s==1时就不同了，这时后手只能转变的成s==0，别无选择
那么如果b是必胜态的话，先手可以把s转移到为1，如果是必败态可以转移至0
那么这个时候n一定是必胜态
但是必须对于n而言s要大于1才行，如果s==1，就必须要继续判断b的必胜必败性了
判断出b的状态后，只需取反即可
poj 1704
这个题目足以说明我没有真正的理解nim的游戏了。。。
看过虽然不是很多问题。。但是发现这类博弈问题，很多都是依靠模仿先手来取胜，，或者是和上一题一样，不给后手选择的机会。。
我们先看一种特殊局面
就是可一把小球分成n/2组，每组的2个小球相互临近，如果n为奇数，那么在0的位置再增设一个不存在的小球
这样种特殊情况，我们可以保证先手必败
那么这就可以转换成为nim的游戏了不过就是n/2+n%2堆小石子，每堆小石子的个数是a[i+1]-a[i]-1
然后求游戏的和就可以了，，至于是真没想到这一点的，，嗯，是参考了别人的。。
poj 2311SG函数的运用
SG(s)=mex{SG{s1}^SG(s2)}，s1，s2为s的子局面
必胜利的局面毫无疑问就是当有一边为1时，显然可以切出(1,2)
递归求解即可
相关阅读
转载说明 https://www.cnblogs.com/Wolfycz/p/8430991.htmlhttps://www.luogu.org/blog/Wolfycz/qian-tan-suan-fa-bo-yi-lun-zon