Bash游戏

和,有颗石子,每次可以取颗,其中,求是否能赢.

考虑直接令石子数量为状态,有,注意到当且仅当.

我们使用数学归纳证明:

当时,显然成立.

而对于,如果,那么集合中一定满足.

也就是满足,那么.反之,一定存在.

Nim游戏

和,有堆石子,第堆石子有个石子.每次可以任选一堆取走若干个石子,最后不能取的人输.求先手是否必胜.

注意到如果均等于一定先手必败.考虑令(即为全游戏的值),那么先手必败当且仅当.

证明:

只需证明当时一定存在一种方法使得.

考虑的最高位为第位,那么一定存在一个的第位为.将它改为,然后这个的后面几位可以随意更改.

Example1(Nimk游戏)

和,有堆石子,第堆石子有个石子.每次可以任选不超过堆取走若干个石子,最后不能取的人输.

将写成二进制,如果每一位的的个数均是的倍数,那么先手一定必败.道理是差不多的.

Example2(Multi-Nim游戏)

Nim游戏,但是玩家每回合可以将任意一堆石子数量大于等于的石子堆分成任意两堆不为空的石子堆.没法操作的人输.

本质仍然是SG游戏,我们正常做就行.

.

找一下规律可以发现:

或

不妨设当时结论成立.

当时,前半部分一定是取遍了.

但是一定不存在和满足并且.讨论一下和在意义下的值就会发现不可能.

其他的是同理的.

SG游戏

个DAG,每个DAG只有一个起始点,起始点上有一枚棋子.和每次可以选一个图,将上面的棋子沿DAG移动一条边,不能移动的人输.

直接使用.

那么先手必败当且仅当所有DAG初始节点的SG异或起来是.

首先如果,那么,使得且.可以发现这就如同Nim游戏了.

但是与Nim游戏不同的是,可能,但是仍然可以转移到.

但在这种情况下,我可以继续转移到一个使得,因此异或值不变.

Example1(Anti-SG游戏)

SG游戏,但是不能取的人赢.

SJ定理:

先手必胜当且仅当下面两个条件满足一个:

  1. 游戏的SG函数不为且游戏中某个单一游戏的SG函数大于.

  2. 游戏的SG函数为且游戏中没有单一游戏的SG函数大于.

如果没有单一游戏的SG函数大于,那么显然游戏的SG函数为就赢了,否则就输了.

而如果SG函数为且存在某个单一游戏的SG函数大于,一定是输的.

因为这个情况下,后手先按照正常游戏压着先手,最后一定会剩两堆一样大于的,无论你怎么选,对手都可以压着你.如果你把一堆全选了,此时对手就可以把另一堆剩下一个,这样就必输;如果你把这一堆选的只剩下一个,对手就可以把它那一堆全选了,这样就也是必输的.

Example2(Every-SG)

SG游戏,但是每次每个能移动的游戏都必须移动,不能移动任何游戏的人输.

对于每个子游戏,如果先手必胜,先手一定会尽可能多争取时间.

反之,先手一定会尽可能早结束游戏.

在上dp的时候除了我们再加一维表示时间耗费,就可以dp了.

Example2.5(Every-SG)

n个游戏,每个游戏两堆石子,每次可以从大的那堆中取小的那堆石子大小的整数倍的石子.

直接套用Every-SG的做法就行.

Example3(Nim on tree)

一棵有根树两个人,每次可以挑一棵真子树删掉,不能操作者输.

结论:.

考虑归纳假设.如果只有一个儿子.那么要么将子树全删,要么删一部分,有:

而如果有多个儿子,则每个儿子都相当于是一个SG子游戏,异或起来即可.

另一种理解方式:考虑只有一个儿子的情况,那么相当于这个儿子的所有状态都向终止节点连了一条边,终止节点的为,而显然图中的其它节点的均要.

Example4

个有根仙人掌,保证所有的环与树的结构只有一个公共点(环只有一条连到环外的边).

两个人分别操作删边,与根不连通的边都被删掉.

结论:奇环,偶环.

这么考虑:边数为的链的为.

而拆开奇环后,你得到的两条链奇偶性一定相同,因而不可能得到.偶环同理,不可能得到.

Example5

无向图,每次删掉一条边以及与根节点不连通的部分,无法操作者输.

考虑Example2.

Fusion定理:将偶环替换成一个新点,奇环替换成一个新点连出去一条边,做边双.对于一个边双,值只和他边的奇偶性有关.证明大概和上面一样.

斐波那契博弈

一个数,两个人轮流令他减去一个数,第一次不能减完,每次减的不能超过上一次的两倍.

不能操作者输.

结论为:当且仅当是斐波那契数时,先手必败.

考虑归纳证明:

先证明当是斐波那契数时必败,不妨假设,

考虑将看成两堆,因为如果第一次取走了大于颗石子,由于,则后手第二步可以全取走,必败.

并且一开始先手一定要在堆取石子,原因是如果取了大于颗石子,由于.这样下一步后手就可以全取完.

那么现在先手应该开始取这一堆,如果在这一堆取的过程中,先手一直取得不超过剩下的数,那么根据归纳假设,后手一定可以取走堆的最后一个石子,此时局面变成了只剩颗石子.只要此时先手不能一次取走颗石子,先手就必败.而后手最后一步拿走石子最多会拿走的石子,但是,,因此一定不可能.

否则,仍然是先手取走了全部石子,又当了先手取的石子.仍然是必败的.

齐肯多夫定理:任意一个正整数都可以被表示成若干不连续的斐波那契数之和.

设,其中,先手取走.由于,因此后手接下来无论如何不可能取得大于等于,问题转化为一堆大小为的石子,此时先手必败.因此原问题的先手必胜.

二分图博弈

给出一张二分图和起点,和轮流操作,每次操作只能选与上一个被选的点相邻的点,且不能选已经选过的点.

考虑二分图的所有最大匹配,如果在所有的最大匹配的方案中都包含了起点,那么先手必胜,否则先手必败.

证明:

如果所有匹配都包含,那么只需要每次走到一个和匹配的点即可.无论如何不可能走到一个不在最大匹配中的点,不然,我们将路径全部取反,就得到了一个最大匹配不变但不包含的点,与假设不符.

而如果存在一个匹配不包含,如果仍然第一步走到一个和匹配的点那么一定能想办法走到一个不在当前选择的最大匹配中的点而在一个不包含的最大匹配中的点,于是必胜.

Example1([2022qbxt国庆Day5]C)

显然,一个人敢抢金条当且仅当没有人敢抢他的金条.假设表示目前集合中的所有人都已经离场了,而目前金条在手中,金条会不会被抢.显然,如果满足,也就是金条在手里不会被抢,那手中的金条必定会被抢.

将这个抢的过程看作二分图博弈中走到相邻的点的过程,于是这个问题等价于二分图博弈.也就是说,如果二分图博弈先手必胜,那么第一个拿到金条的人一定会被抢.

因此,我们需要找到所有与匹配的可能出现在最大匹配中的边,对应编号最小的那个点,金条最后一定在他手里.(第一步这么走后,一定能构造出)

这个怎么构造呢,我们考虑先跑一遍dinic求最大匹配,然后做一遍tarjan缩点,然后如果和并未匹配,那么我们判断二者是否在一个强连通分量中,如果在,那他们可以被匹配.

至于判断是否一定在其中,只需要先删去,跑dinic,再在残联网络上加上,判断是否有新的增广路.

树上博弈

Example1(zr[23省选10连 day1] Clashmas)

注意到删点对树形态的影响,考虑重心

  1. 为奇数,重心为后手点.

注意到此时后手一定可以通过一些方式维持重心不变,因此后手必胜.

  1. 为奇数,重心为先手点.

我们不妨设先手是A,后手是B.

考虑一个事实:对于这样一棵树,我们删着删着一定会出现一个时刻使得此时为偶数,有两个重心(比如最后只剩下两个点的时刻),根据(4)和(5)的讨论,此时胜负已分.而且不难注意到此时A变为了实际上的后手.

根据(5),如果B掌控了任意一个重心,那A就输了.因此A必定要使当前局面的两个中心均为A的点.考虑原重心的所有儿子,它们有的是A点,有的是B点.由于树的重心的性质,树的重心的移动一定是一点一点挪的,也就是说第一次出现上面的局面的时候,两个重心必有一个是原重心,另一个是原重心的儿子,接下来A和B就要对于另一个重心能取到哪个儿子做争夺.我们不妨设A的点的集合为,B的点的集合为.以原重心为根建树,设其所有儿子组成的集合为,不难发现A能胜利(也就是让两个重心全都属于他)当且仅当.

原因很简单:A和B必然每次都会去杀属于对方的子树中最大的那棵.由于A有着先手优势,因此只要满足上面的条件,A总能获胜.

  1. 为偶数,唯一重心,重心为后手点.

类似(2)的讨论,最后一定有某个时刻使得此时为偶数,有两个重心(比如最后只剩下两个点的时刻),此时A仍然是先手,根据(5),只要他掌控一个重心就可以获胜.

类似地,不难发现胜利条件等价于(2).

  1. 为偶数,两个重心,重心均为后手点.

注意到此时整棵树分为两个大小相等的部分,因此后手一定可以维持这个场面不动,后手必胜.

  1. 为偶数,至少有一个重心是先手点.

注意到此时先手一定存在一种方式开局,使得重心仍为这个先手点,这样就转化为第一种情况,先手必胜.

散题

Problem1([CSP-S2020]贪吃蛇)

首先注意到,如果一个蛇吃完后还不是最小的蛇,那它一定会吃.因为被吃的蛇是单调不降的,而吃蛇的蛇是单调不增的,因此下一个蛇如果要吃,那一定会比它还小,所以至少会先被吃掉,而那条蛇会被吃掉,它就一定不会选,所以无论如何这条蛇都不会被吃掉.

我们考虑如果吃完后变成了最小的蛇后会怎么样,我们设为还剩条蛇的时候能不能吃,那的话,要么,要么吃完后不是最小的,要么.

递归做就好了.另外这题需要复杂度,需要用几个队列/双端队列维护.

Problem2([AGC023D]Go Home)

首先,最后一个人要么是最左边的,要么是最右边的.而显然这两边中人数较少的一个将会是最后一个到家的,那么这个人的目标就是帮助另一边的人尽可能快到家,于是会帮着它投票.以此类推不断递归下去.

Problem3(牛客38727E)

首先考虑如果有人作为第个人复读了,那接下来复读一定不会被惩罚,于是没复读的都会复读,这样这个人就必死.于是最多只会复读个人.

继续思考,如果有人作为第个人复读了会怎么样,后面的人也都不会被惩罚了,于是也会继续复读.

以此类推,会发现最后只会有个人复读,并且一定是前在一轮内复读完.

Problem4(arc155D)

考虑直接转移,但是有可能出现在原地转的情况,注意到这种情况我们只需要记录表示当前的是,的倍数还剩下个,然后做转移,再进一步发现我们只关心的奇偶性.于是记即可.

这题给我最大的启示是,我们不能假定让双方共同遵守一个"君子协定",博弈论最重要的就是博弈,不能说我们最后再选倍数之类的,他的转移路线会变化的.

Problem5

给一个“日”字型图,七条边,每条边有一堆石子.每次可以选任意多条不构成环的边,然后将这些边上的石子堆取走任意多个石子.求先手必胜策略,以及如果每条边的石子数量在,那么有多少种先手必胜的情况.

考虑将这个图分成三部分,上面三条边,中间一条边,下面三条边.那么这三部分一定不能全选至少两部分,不然会构成环.反之一定构不成环.

先手必败当且仅当,这三部分内部的边上石子均相等,并且所有边异或值为.

否则,考虑将上部分和下部分三条边先全改成相等的,会修改较大的两条边.

接下来,我们剩了三条边,我们只能选择改其中一条,使得他们仨异或值为.

换句话说,我们现在有,我们要将其中一个改为,其他不变,使得他们仨异或值为.和Nim游戏类似,假设他们仨异或值的最高位为.那么一定有一个的第位为,将它改为,后面就可以随意变换.

思路具体怎么想到的呢,可以发现整个图只有三个环,并且这三个环都可以由这几部分组成.接下来就可以每个部分的求个交,用FWT做一遍异或卷积.数位dp也可以做.

Problem6

Nim游戏,但是每堆石子有一个.如果这堆石子剩个每次最多取个石子.求先手是否必胜.

结论是

SG(n-\lfloor\frac n k\rfloor,k)&n\ne 0(\mod k)\

\frac n k&n=0(\mod k)\

\end{cases}\

考虑数学归纳就可以证明.

然后我们就只需要对于是否大于讨论一下,如果暴力,最多只会做次.否则,意识到此时可以通过求一个区间,满足均相等,加速一下.这种区间最多只会有个.

Problem7

一个数,两个人轮流令他减去一个数,第一次不能减完,每次减的不能超过上一次.不能操作者输.

先手必败当且仅当,不然,每次选lowbit即可.

Problem8

A和B,有颗石子,每次可以取颗,其中.

仍然令石子数量为状态,注意到当且仅当,也即.首先,注意到:

设,其中:

当时,原式.反之.原式.因此数学归纳即可证明.