博弈论蓝紫黑

· · 算法·理论

树上博弈

Game On Tree 3。

二分答案 mid。

考虑 dp。

直接转移即可，合法仅当 $f_1\ne 0$。 [Submission](https://atcoder.jp/contests/abc246/submissions/48604356) [哈利波特与死亡圣器](https://www.luogu.com.cn/problem/P4572)&[LUK-Triumphal arch](https://www.luogu.com.cn/problem/P3554) 二分答案 $mid$。 考虑 dp。 $f_u=\max(\sum_{v\in son_u}f_v-mid,0)+1$。 直接转移即可，合法仅当 $f_1=1$。 [Code](https://netcut.cn/p/757d2112aa2d4723) [Game on Tree 2](https://www.luogu.com.cn/problem/AT_abc218_g) 记 $r_x$ 为根节点到 $x$ 的中位数。 设 $f_{x,0}$ 表示现在为先手，得分最大值。 设 $f_{x,1}$ 表示现在为后手，得分最小值。 如果 $u\in leaf$，则 $leaf_i=1$。 则有转移 $$ \forall leaf_u=1,f_{u,0}=f_{u,1}=r_u $$ $$ f_{x,0}=\min_{v\in son_u}f_{v,1} $$ $$ f_{x,1}=\min_{v\in son_u}f_{v,0} $$ $r_x$ 可以直接用平衡树求。 [Summission](https://atcoder.jp/contests/abc218/submissions/51197503) [Tree Tag](https://www.luogu.com.cn/problem/CF1404B) 显然的，如果 $dis_{a,b}\le da$，则 Alice 胜。 若 $2da\ge db$，说明 Bob 总会被 Alice 拉进死角原地趋势。 同理，Alice 也可以占据直径中点，Bob 将被无死角打击，也就是说 $2da\ge \max$。 [Code](https://netcut.cn/p/2fcee84616fece3c) [另一侧的月](https://www.luogu.com.cn/problem/P8347) 通过观察出以下结论： - 若所有节点的度数都为奇数，则先手必败。 - 反之先手必胜。 考虑证明。 设先手必败态为 N，必胜态为 P。 - 则有 N 的后继状态均为 P。 - P 的后继状态含有 N。 由于原树中的度数都为奇数，则删掉一条边之后的联通块的根度数为偶数，N 的后继状态均为 P 成立。 由于一棵树仅有有限个度数为偶数的节点，所以钦定一个度数为偶数的点，它的一棵子树中有且仅有奇点。（假设子树中仍有偶点，那么就指定这个点为根）。 [Code](https://netcut.cn/p/fc1baaa5126b8baa) [Black and White Tree](https://www.luogu.com.cn/problem/AT_agc014_d)。 看题解区都写的好麻烦。 如果一个叶子节点的父亲被染白，则其必然是黑色点，相当于删去这两个节点，这样显然是最优的。 不断执行操作。 如果还有点没有被删除，则先手获胜。 否则后手获胜。 [Submission](https://atcoder.jp/contests/agc014/submissions/46487013) ### 最优化 [Fox and Card Game](https://www.luogu.com.cn/problem/CF388C) $\text{Difficulty:}2000$。 首先，A 会取牌堆牌的前 $\lfloor\dfrac{n}{2}\rfloor$ 张牌，B 会取牌堆牌的后 $\lfloor\dfrac{n}{2}\rfloor$ 张牌。 - 若第 $i$ 堆牌为奇数，则将其插入大根堆。 - 若第 $i$ 堆牌为偶数，则不进行计算。 最后两个人轮流取大根堆里的值。 直接模拟即可。 [Submission](https://codeforces.com/contest/1147/submission/238237383) [Thanos Nim](https://www.luogu.com.cn/problem/CF1147C) $\text{Difficulty:}2000$。 结论： - 最小堆的个数大于 $\dfrac{n}{2}$，先手必败。 - 反之先手必胜。 若最小堆的个数大于 $\dfrac{n}{2}$，先手必然会选到至少一个最小堆，此时最小堆数量必然小于 $\dfrac{n}{2}$，此时后手选择非最小值的 $\dfrac{n}{2}$ 堆石子，把它们变为最小值，此时回归原状态，先手必败。 反之可得先手必胜。 [A Coin Game S](https://www.luogu.com.cn/problem/P2964)&[A Coin Game](https://www.luogu.com.cn/problem/SP5271) 优化不是很好想。 记 $f_{i,j}$ 为上一轮取了 $j$ 枚，还有 $i$ 枚的先手最大值。 则有转移 $f_{i,j}=\max_{k\le 2j} \sum_{l=1}^ia_i-f_{i-k,k}$。 显然可以优化到 $n^3$ 的复杂度，但无法通过此题。 由于 $f_{i,j}$ 和 $f_{i-1,j}$ 差不多，令 $k=2j-1$，则有 $f_{i,j}=\max(f_{i,j-1},f_{i-k,k},f_{i-k-1,k+1})$。 [Code](https://netcut.cn/p/45bc163cc377d8c3) [九省联考 2018 一双木棋 chess](https://www.luogu.com.cn/problem/P4363) 发现对当前状态有用的状态不会太多（一个类似楼梯的形状），最多 $C_{n+m+1}^{n}$ 种情况。 于是状压记忆化搜索即可。 压的是 $11$。 [Summission](https://loj.ac/s/2061460)。 [CF1628D2](https://codeforces.com/problemset/problem/1628/D2) 先说 D1 做法。 记 $f_{i,j}$ 表示 $n=i,m=j$ 时的答案。 有 $f_{i,i}=ik$。 如果 Bob 选择的数字为 $x$，则 $f_{i,j}=\min(f_{i-1,j}-x,f_{i-1,j-1}+x)$。 这时选择 $x=\dfrac{f_{i-1,j}-f_{i-1,j-1}}{2}$，这时 $f_{i,j}=\dfrac{f_{i-1,j}+f_{i-1,j-1}}{2}$，是最大值。 答案即为 $f_{n,m}$，时间复杂度 $\mathcal O(n^2)$，可以通过 D1，[D1Submission](https://codeforces.com/contest/1628/submission/258656209)。 D2 做法： 考虑枚举每个 $f_{i,i}$ 的贡献。 首先会经历 $n-i$ 次变为 $\dfrac{1}{2}$，也就是 $\dfrac{1}{2^{n-i}}$。 在考虑会加几次贡献。 发现相当于站在 $(i+1,i)$ 点（因为走到 $(i+1,i+1)$ 会算重贡献），每次可以变为 $(i+1,j)$ 或者 $(i+1,j+1)$，问到 $(n,m)$ 的方案数。 由于一共会走 $n-(i+1)$ 次，选择 $m-i$ 次给 $j$ 加一，利用组合数可以求得方案数量为 $\binom{n-i-1}{m-i}$。 结合 D1 做法，答案为 $k\sum_{i=1}^ni\binom{n-i-1}{m-i}

时间复杂度 \mathcal O(n\log n)（更优秀的组合数预处理可以 \mathcal O(n)），可以通过 D2，

D2Submission

序列

Decrementing

最优策略是：选一个偶数，由于原序列中的最大公约数是 1，则必含有一个奇数，所以后手只能改变一个一个数的奇偶性，先手仍处于必胜态。

由于操作次数不会超过 \log W 次，算上 \gcd 的复杂度为 n\log^2W。其中 W 为值域。

Submission

Submission

转化

AGC002E Candy Piles

将 a 递减排序，以下以 a=\{7,7,7,6,4,4,4,2,2\} 为例。

图片来自官方题解。

问题可以转化为在网格图上走。

操作一相当于往右走一格，操作二相当于往上走一格。

走到边界时输。

用必胜/败填充网格得到上图，表示当轮到我时已经在该位置时必胜/败。

观察得到同一对角线上的点的胜负态一样，且除原点对角线外相邻对角线的状态相反。

则可以快速求原点的胜负态，见右图。

Submission

人人尽说江南好

首先有结论：答案肯定会分为一堆 n\bmod m 和 \lfloor \dfrac{n}{m}\rfloor 堆 m，操作次数为 n-\lfloor \dfrac{n}{m}\rfloor -[n \bmod m\ne0]。

证明较易。

具体的，判断先手合成两个 1 或者合成 \max 和 1。

其实就是巴什博弈。

Code

杂

椎名真昼

发现一个人若在本次操作不能获胜，则在下一次操作时仍然不能获胜，因为对方重复他的操作即可。

问题转化为：

考虑判断这个问题。

现将原图缩点，若一个环中存在异色点，我们直接判断平局，因为无论如何操作必然仍存在异色点。

找到任意一个黑色点对其进行操作，若可以，则 Alice 获胜，否则 Alice 无法获胜。

记入度为 0 的节点为“根”，因为图中无环，则。

则若有至少一个根为白色，则 Alice 必然操作该节点导致 Bob 也必然操作该节点，所以 Bob 在此时必胜仅当所有点都是白色。

若所有根节点均为黑色且存在至少两个根，则 Bob 必胜仅当 n=2，因为若 n>2，Alice 可以选择一个非根节点使得 Bob 无法一次操作两个黑色根节点。

若所有根节点均为黑色且存在一个根，所以根与所有节点联通，则 Alice 可以操作某个根节点以外的点使得图中节点不是全黑，如果只有两个点，一黑一白，黑点连向白点，则 Bob 必胜。

Alice 的选点策略如下：

这也解释了为什么有 Bob 的必胜态情况。

代码先咕咕着，有时间和精力再去写。

Nim 变种

小约翰的游戏&John

证明先咕咕着。

结论是特判 1 的 Nim 游戏。

Code

新Nim游戏

首先先手必胜，因为实在不行可以只剩下 1 堆。

我们对于剩下的情况，从大到小考虑每个数。

如果将其插入线性基失败，则说明去掉它可以使异或和为 0，则我们需要在第一轮取走。

Code

KAM-Pebbles

本题为经典的阶梯博弈变种。

因此先引入阶梯 Nim 问题。

阶梯 Nim 问题是指，有 n 堆石子，每次我们可以从第 i 堆的石子中拿走一部分放到第 i-1 堆中，或者把第 1 堆中的石子拿走一部分，无法操作的人算输。由于在偶数位置移先手可以将其继续移到偶数堆，对奇数堆没有影响，因此阶梯 Nim 的游戏结果与只看奇数堆的石子数的普通 Nim 结果相同。

再看本题，可以对石子堆数进行差分，取走一堆相当于将一些石子挪到 i+1 堆中，因此与阶梯 Nim 游戏相反。

Code