博弈练习

理论后面再补吧

[省选联考 2023] 过河卒

我们将其局面抽象为一张图,然后不难发现没有环的情况我们直接\(dfs\)就可以了

如果有环的话,其对应的应该就是\(Tie\)的情况,具体的就是如果我们在访问\(x\)的祖先时\(x\)就可以达成死循环的局面,但这个不好维护

反过来考虑,我们直接对可以直接判断的局面作为起始节点跑个类似于拓扑的结构

如果是\(u\)必败,\(v\)则为必胜,\(u\)必胜,我们记录\(v\)还可以转移的边,如果没了\(v\)就是必败

最后没访问到的就是\(Tie\)

有点卡常

[POI1999]多边形之战

降智题

这个多边形的每条边作为无向图上的每条边,然后你会发现操作就是删除叶子节点

如果黑色的就是叶子先手必胜

否则俩个人一定要删\(n-1\)(\(n\)是树的节点数)次,直接\(\&1\)即可

BZOJ3895

如果没有大小为\(1\)的石子堆,理论上我们可以操作的次数是\(Sum+n-1\)

如果\(Sum+n-1\)是奇数,\(A\)一定有办法使其一直为奇数,因为每次\(Sum+n-1\)都只\(-1\)

且\(A\)一定会避免出现\(1\)的石子堆

对于\(Sum+n-1\)为偶数,其实也差不多,\(A\)因为先手所以无法改变,因此\(B\)必胜

如果出现了\(1\)的石子堆,取\(1\)这个石子堆会使\(Sum+n-1\)一次\(-2\)

如果有一个\(1\),\(A\)可以选择\(-1\)或\(-2\),因此\(A\)必胜

如果有两个\(1\),如果\(A\)本就必胜,\(A\)可以将两个\(1\)和在一起

如果必败,\(A\)无论怎样操作,\(B\)同样可以操作回来

因此可以分\(1\)的奇偶

如果全是\(1\),或者一个\(2\)和全部\(1\),只有当\(1\)的个数是\(3\)的倍数是\(B\)才可能赢

谁能赢呢？

\(n\)是偶数是必胜

如果没封口,以上易证

考虑封口的情况,如果是\(A\)决定往哪边封口

则现在已经有奇数个格子

如果一口是偶数,\(n\)是偶数,另一口是奇数则\(A\)可以往奇数的那边跑

如果一口是奇数,一样的

如果\(n\)是奇数,那两口都是偶或奇,如果是奇\(A\)就赢了？

好像\(B\)可以避免这种情况,在封口前延迟封口即可

本质是在二分图上博弈,结论是当最大匹配包含\(S\)时先手必胜

[ZJOI2009]染色游戏

首先对于这些翻棋子的游戏,都有个结论,局面的\(SG\)为所有正面棋子单独存在的\(SG\)的异或和

对于单个棋子\((i,j)\)的异或和,分类讨论一下

如果\(i=1\)或\(j=1\),考虑另一维所处位置\(x\),结论是\(SG(x)=lowbit(x)\)

考虑归纳证明,如果\([1,2^k-1]\)满足

对于\(x\in[2^k,2^{k+1}-1]\),往后依次延伸,你取到\(x-2^{k}\)的时候,恰好和\(x-2^{k}\)往后取是一样的,然后你还会发现这一段\(SG\)的异或和为\(0\),因此\(SG(x)=SG(x-2^k)\)

我们对于每个\(x\)一次减去它的最高位,最后剩下的就是\(lowbit(x)\)

如果\(i,j\)均不为\(1\),\(SG(i,j)=2^{i+j-2}\)

同样考虑归纳证明

如果\((i-1,j)\),\((i,j-1)\)均满足条件

对于\((i,j)\),首先\((i-1,j)\)出发的点能取到的\(SG\in[0,2^{k}-1]\),再异或一个\(2^k\)

也就取到了\([2^{k},2^{k+1}]\),如果再取\((i,j-1)\),那有可以取\([0,2^{k}-1]\)

因此\((i,j)\)能取到\([0,2^{k+1}]\)

最后用\(bitset\)算即可

「BZOJ1457」棋盘游戏

这个就有点类似与\(SG\),不过胜利条件改为第一次到达\((0,0)\)

如果有可以一步到达的那\(A\) 必胜

否则两个人一定会把棋子堆到\((2,1)\)或\((1,2)\),这样就转化为不能挪动的输,直接\(SG\)求即可

Moving Pebbles

首先如果\(n\)为偶数且数量相等的堆一一对应,我们直接模仿就行了,先手必输

这里我们排个序然后把能配对的删去

剩下的如果\(n\)时奇数,我们把先手最大的取完,然后移动去填\(2i-1\)和\(2i\)的差,可以证明填完一定有剩余,因为最大的等于差分的前缀和加上第一个

如果\(n\)时偶数,一样的,把最大的移到和最小的相等,然后再用多余的填差分,这样也一定时够的

[SDOI2011]黑白棋

很明显每对黑白棋子之间可以看成一个\(Nim\)堆

然后这就是可\(K-NIM\)游戏,结论是每个二进制为为\(K+1\)的倍数时后手必胜

然后直接对位\(Dp\)即可

[HAOI2015]数组游戏

注意到\(\lfloor\dfrac{n}{x}\rfloor\)相同的\(x\)的\(SG\)是相同的

因为\(\lfloor\dfrac{n}{xk}\rfloor=\lfloor\dfrac{\lfloor\dfrac{n}{x}\rfloor}{k}\rfloor\)

考虑直接对\(n\)整除分块,然后块于块之间,我们考虑从后往前考虑直接前缀\(SG\)然后取\(MEX\)

对于块\(\lfloor\dfrac{n}{x}\rfloor\),\(\lfloor\dfrac{\lfloor\dfrac{n}{x}\rfloor}{k}\rfloor\)同样可以整除分块,然后预处理出所有块的\(SG\)即可

有点卡常

CF98E

先手为\(0\),那他一定会直接猜,如果后手为\(0\),那先手就赢了

如果现在有状态\((n,m)\),他现在有两种选择

一是直接猜,赢的概率是\(\dfrac{1}{m+1}\)

二是指定一张,我们暂时不考虑指定自己已有的牌,那就有\(\dfrac{1}{m+1}\)输,有\(\dfrac{m}{m+1}(1-(m-1,n))\)的概率赢

小丑了,可能可以指定自己的牌从而达到欺骗的作用

对于这种情况,我们不妨考虑如果\(B\)不傻,那\(A\)的欺骗等同于告诉\(B\)自己的手牌

还有一点很麻烦,如果\(A\)或\(B\)在不清楚桌上的牌时直接猜怎么办

似乎这样做一定不优,额,证明就算了吧,感觉有点牵强

因为两者一定不会不清楚情况直接猜,所以对于\(B\),一定是在是否信任\(A\)的情况下进行猜测

我们可以据此列出一个\(A,B\)决策不同时\(A\)的胜率\(f(n,m)\)的表格

然后对于\(A\),\(B\),我们分别设\(p,q\)为出手牌,是否信任的决策频率,这个\(p,q\)是可以随时调整的?不过对于混合策略,我们姑且认为\(A,B\)有\(p,q\)的概率做出对应决策

由此\(A\)的胜率即为\(g(n,m,p,q)=(1-p)[\dfrac{m}{m+1}(1-f(m-1,n))+\dfrac{1}{m+1}(1-q)]+p[(1-p)(1-f(m,n-1))+q]\)

观察这个式子,对于\(A,B\)可以调整\(p,q\)使得自己的收益最大,这就形成了一个纳什均衡,也就是当一个人的固定时,另一个人的策略也是固定???

反正答案\(f(n,m)=Min_{q=0}(Max_{p=0}g(n,m,p,q))\)

然后考虑固定\(q\),\(g(n,m,p,q)\)是个关于\(p\)的一次函数,所以它的\(Max\)是在端点\(p=0,1\)时取得

我们画出\(p=0,p=1\)的函数,其实也就是关于\(q\)的一次函数

\(p=0,\dfrac{m}{m+1}(1-f(m-1,n))+\dfrac{1}{m+1}(1-q)\)

\(p=1\),\((1-q)(1-f(m,n-1))+q\)

观察到\(p=0\)时斜率小于\(0\),\(p=1\)时斜率就是\(f(m,n-1)>0\),所以最后的答案就是函数的交点,我们只需对于每个\((n,m)\)解出\(q\)即可