写的前面都比较基础,后面有一些很鬼的题。

SG函数

简单回顾一下函数:

,其中的后继局面。

局面的合并的为所有局面的函数的异或和。

非零则先手胜,否则先手负。

套路

几个常见的Nim游戏套路:

几个常见的分析套路:

翻硬币问题

假设有枚硬币排成一排,有的正面朝上,有的反面朝上。

游戏者根据某些约束翻硬币(如:每次只能翻一或两枚,或者每次只能翻连续的几枚),但他所翻动的硬币中,最右边的必须是从正面翻到反面,不能翻的人输。

那么局面的值等于局面中每个正面朝上的棋子单一存在时的值的异或和。

各种图的删边游戏

以下游戏均要求复杂度

一般树上删边游戏

给定一棵有根树,每次删掉一条边,把不与根节点相连的部分删除。不能操作的人输。

解法:

考虑打表分析得到,其中的儿子。

很简单对吧。

圣诞树上删边游戏

定义一个圣诞树:在树上挂几个环,每一个环只与树有一个公共点,环与环之间无公共边。

仍然玩删边游戏。

解法:

对于长度为奇数的环,去掉一条边后得到两条长度同奇偶的链,值异或后不可能是奇数,因此

对于长度为偶数的环,去掉一条边后得到两条长度异奇偶的链,值异或后不可能是偶数,因此

还是很简单对吧。

仙人掌上删边游戏

现在要在仙人掌上玩删边游戏。

怎么做??

解法:

考虑所有环下面的部分在缩环以后会变成啥样。

长度为偶数的环缩环后,所以删去这个环并把剩余部分接上去,答案的不变。

长度为奇数的环缩环后,造一个新点接回去,然后发现下面的部分是直接影响上面的点的,而不影响新点的值,则也接上去即可。

……仍然不难嘛

无向图上删边游戏

现在做无向图的删边游戏,如果删掉一条边后某部分和根不再联通则丢弃。

解法:

考虑把仙人掌的算法移植过来:

找寻每个简单环并缩掉,然后所有旧边都接回这个环的根,然后继续做。

可是复杂度是的。

使用融合原则可以得到偶数个点的边双会缩成一个点,奇数个点的边双缩掉以后会额外挂一个点。

用Tarjan算法即可。

动态减法游戏

1x 动态减法游戏

有一个整数,两个人想让它变成。首先,第一个人需要把减掉一个数。之后双方轮流把减掉一个正整数,但都不能超过先前一回合对方减掉的数,减到的一方获胜。

问谁会获得胜利。

同时询问如果先手胜,在第一次最小可以减掉多少

做法:

我们发现是奇数的时候只要第一个人选择减去,那么他一定能赢。

这是一个优秀的分做法。

正经一点,做法:

打表找规律,发现答案是的时候后手必胜。

只需要考虑怎么证明:

首先如果,那么先手减去得到,那么在后位都为,这样一来后手不能再次减去。因此后手会减去一个的数,这时候由于,那么先手可以继续这么做下去直到减到为止。同时因为后手每次减的数都不足剩余数,那么后手不可能胜。

接下来如果是,那么操作方减去任何一个不足的数都可以使得后手按照必胜策略继续操作下去,这样必败。

优秀的证明。

接下来考虑做二问。

显然先手胜的时候减去合法,同时减去一个小于的数时都又可以使得后手按照必胜策略继续操作下去,那么在第一次最小只能减小

做完啦!很有趣对不对!

2x 动态减法游戏

又有一个整数,两个人想让它变成。首先,第一个人需要把减掉一个数。之后双方轮流把减掉一个正整数,但都不能超过先前一回合对方减掉的数的两倍,减到的一方获胜。

现在我连分做法都不会了怎么办??

打个表!发现答案竟是斐波那契数列的时候必败!

怎么证?考虑用上一个证法:

不是斐波那契数时,一定可以拆成不少于个不相邻的斐波那契数之和。定义斐波那契分解下的为分解出来的所有不相邻斐波那契数中最小的一个。同样的先手先减去得到,那么现在后位都为,这样一来后手不能再次减去(因为超过两倍)。因此后手会减去一个的数,那么先手依然可以继续这么做下去直到减到为止。同样的因为后手每次减的数都不足剩余数,那么后手不可能胜。

是斐波那契数的时候任意一个操作都使得后手可以按必胜法操作,必败。

简直有毒……

海盗分金

完了完了,蛇皮的一题……

题面

个海盗来分块金子。

海盗的编号是从。从第号海盗开始,他们会依次提出自己的分配方案。如果半数及以上的人(包括半数)赞成他的方案,则方案通过,开始分金子;否则方案不通过,海盗们就会把提出方案的那个人分尸吃掉,由下一个人继续提出方案。

海盗的原则:

先保证自己的生命安全,再想办法得到最多的金子,最后还要努力吃掉更多的人。

现在问对于每一个海盗,他能否活下去?如果能的话,他至少可能分到多少金子?

海盗的逻辑分析

从两个人入手:

两个人时,拿走所有块金子,并且自己投自己,所以完结。

三个人时,想的是只要死了我就拿到所有而且不会死,那我怎么也不会投。因此为了保命只能收买的想法是只要死了我的收益就是,那么只要给我至少一个,我就投。因此最终局面是个,个。

四个人时,同样会选择去收买个人时收益为,并且也只需要给他个。

……

金子足够

如果金子足够,照如上的推理最后一个人为了保命,会拿出收买所有奇偶性和他相同的人,因为这些人在少一个人的时候拿不到金子,现在一旦拿到,就会力挺最后一个人。

即使有第或者第个人,这个人也会为了保命把所有块金子拿去收买人,虽然自己得不到金子。

金子不够

现在假设人数多于,假设来了,由于已经可以保命,那么他们本意就不会投,除非被收买,但只能额外收买个人,他必死无疑。

假设来了仍然本意不投,知道一旦死掉自己也会死,所以无论如何都会投,加上自己的一票和收买的的票就可以活下来。

接下来依次来了,但是由于前面的人都已经可以保命,而这个人都不够票,所以都会死。

当来了的时候,收买的票、不投就会死的票加上自己的票就足够票了。

那么这新来的个又不会投票了(除非被收买),只有再等个人来,下一个可以活下来的则是

推到这里已经可以发现了,存活下来的是

关于至少分到数量

当金子足够,即,可以得到前面奇偶性相同的各拿,最后一个拿走剩下的。

当金子不够,后面的人从个人开始都可以从前面所有人中任选个收买,谁也不能保证自己拿到金子,最少分到数量都是

博弈论与匹配

两人轮流沿着边走,不允许重复访问节点,不能移动者输。

这是个经典问题(Undirected Vertex Geography)。

对于该问题有以下定理:

起点 是先手必胜的,当且仅当它在所有最大匹配上。

具体例子可以看LOJ Round #6的T4。