专题训练 - 博弈 I

[CF1396B] Stoned Game

首先我们要观察出来一个显然的必胜态，设 $S=\sum a_i$，如果存在一个 $a_i>\cfrac{S}{2}$，那么先手只要一直选 $a_i$ 就能够获胜了，接下来我们来看 $\forall i,a_i\le \cfrac{S}{2}$ 的情况。

由于每个人都不会想给对面留下一个 $\exists i,a_i>\cfrac{S}{2}$ 的局面（因为这样对面必胜），所以每一步必然就会尝试使得 $\forall i,a_i'\le \cfrac{S'}{2}$。

实际上也确实可以做到这一点：只要每次给最大的 $a_i$ 拿走 $1$ 即可，可以分为最大值有 $1$ 个和 $\ge 2$ 个简单讨论得出。

既然 $\forall a_i,a_i\le \cfrac{S}{2}$，所以每一步必然会有至少两个堆，所以答案只与 $S$ 的奇偶性相关。

[CF1451D] Circle Game

由于局面是高度对称的，所以我们可以往对称轴上来思考。

观察圆内最远能到达的直线 $y=x$ 上的点 $(mk,mk)$，即 $2m^2k^2\le d^2$ 并且 $2(m+1)^2k^2>d^2$，我们来看 $((m+1)k,mk)$ 是否在圆内。

1. 若 $((m+1)k,mk)$ 不在圆内，那么对称地 $(mk,(m+1)k)$ 也不在，于是 $(mk,mk)$ 是 $P$ 态。

   那么 $((m-1)k,mk)$ 是 $N$ 态，$(mk,(m-1)k)$ 也是 $N$ 态，就能推出 $((m-1)k,(m-1)k)$ 是 $P$ 态。

   以此类推，$(0,0)$ 是 $P$ 态。

2. 若 $((m+1)k,mk)$ 在圆内，那么它不可能向上走，那能不能向右？$((m+2)^2+m^2)k^2>2(m+1)^2k^2>d^2$，所以也不能向右，则 $((m+1)k,mk)$ 是 $P$ 态，对称地 $(mk,(m+1)k)$ 也是 $P$ 态，于是 $(mk,mk)$ 是 $N$ 态。

   因为 $(mk,(m+1)k)$ 是 $P$ 态，则 $((m-1)k,(m+1)k)$ 是 $N$ 态，于是 $((m-1)k,mk)$ 是 $P$ 态，则 $((m-1)k,(m-1)k)$ 是 $N$ 态。

   以此类推，$(0,0)$ 是 $N$ 态。

[CF2006A] Iris and Game on the Tree

显然我们可以把这个 $\texttt{01}$ 和 $\texttt{10}$ 看作这个串的 $\texttt{0}/\texttt{1}$ 切换时权值会 $+1/-1$，于是如果最后一个字符和第一个字符相同，那么这个点的权（前面提到的权值的绝对值）是 $0$，否则是 $1$，这就和中间节点无关了。

1. 如果根不是 $\texttt{?}$，那么每个人都会尽量把叶子染成自己希望的那个颜色，设未定的叶子个数是 $m$，那么答案就是既定权值 $+\lceil m/2\rceil$。

2. 如果根是 $\texttt{?}$，设未定的叶子个数是 $m$，

   • 如果既定的 $0$ 和 $1$ 数量 $x_0,x_1$ 不等，设基础权值是 $\min(x_0,x_1)$，那先手总可以用一步定根获得 $|x_0-x_1|\ge 1$ 的收益，如果选叶子的收益 $\le 1$，所以一定会先定根，即答案是 $\max(x_0,x_1)+\lfloor m/2\rfloor$
   • 如果既定的 $0$ 和 $1$ 数量 $x_0,x_1$ 相等，那么定根的收益就是 $0$ 了。如果此时某人选了一个未定的叶子，就会导致对方定根的收益为 $1$，这是我们不希望的；所以我们会选不是未定叶子也不是根的未定节点，直到必须定根，那么答案就是 $x_0+\lfloor (m+y)/2\rfloor$，其中 $y$ 是不是未定叶子也不是根的节点的未定节点数量模 $2$。

具体的证明过程如下：

1. 不妨设根为 $1$，叶子颜色为 $0$ 的有 $L_0$ 个，同理 $L_1,L_{?}$，再设 $I_?$ 是中间的未定节点数量。

   设 $V_I(L_0,L_?,I_?)$ 为 Iris 先手时最终得分，$V_D$ 同理，那么状态转移：

   $$V_I(L_0,L_?,I_?)=\max \begin{cases} V_D(L_0+1,L_?-1,I_?)\quad &L_?\ge 1\\ V_D(L_0,L_?,I_?-1)\quad &I_?\ge 1\\ \end{cases}$$

   同理，$V_D$ 的转移如下：

   $$V_D(L_0,L_?,I_?)=\min\begin{cases} V_I(L_0,L_?-1,I_?)\quad &L_?\ge 1\\ V_I(L_0,L_?,I_?-1)\quad &I_?\ge 1 \end{cases}$$

   我们来用数学归纳法证明 $L_?+I_?$ 为任意自然数时，都有 $V_I(L_0,L_?,I_?)=L_0+\lceil L_?/2\rceil$，$V_D(L_0,L_?,I_?)=L_0+\lfloor L_?/2\rfloor$。

   当 $L_?+I_?=0$ 时，显然成立，接下来我们进行归纳步：

   对于 $V_I$，我们有：

   $$\begin{aligned} V_I(L_0,L_?,I_?)&=\max\left\{L_0+1+\left\lfloor\frac{L_?-1}{2}\right\rfloor,L_0+\left\lfloor\frac{L_?}{2}\right\rfloor\right\}\\ &=L_0+\left\lceil\frac{L_?}{2}\right\rceil \end{aligned}$$

   对于 $V_D$，我们有：

   $$\begin{aligned} V_D(L_0,L_?,I_?)&=\min\left\{ L_0+\left\lceil \frac{L_?-1}{2}\right\rceil,L_0+\left\lceil\frac{L_?}{2}\right\rceil\right\}\\ &=L_0+\left\lceil\frac{L_?-1}{2}\right\rceil\\ &=L_0+\left\lfloor\frac{L_?}{2}\right\rfloor \end{aligned}$$

   证毕。

2. 如果根没有被定，那么我们的状态就应当包含 $L_0,L_1,L_?,I_?$ 了，因为我们总是可以选择下一步是否定根，定根之后就有直接的公式可以计算，所以是否定根可以给我们一个下界。

   说起来比较抽象，写成公式的话，就是：

   $$V_I(L_0,L_1,L_?,I_?)=\max\begin{cases} V_D(L_0,L_?,I_?)=L_0+\lfloor L_?/2\rfloor\\ V_D(L_1,L_?,I_?)=L_1+\lfloor L_?/2\rfloor\\ V_D(L_0,L_1,L_?,I_?-1)\\ V_D(L_0+1,L_1,L_?-1,I_?)\\ V_D(L_0,L_1+1,L_?-1,I_?) \end{cases}$$

   同理，对于 $V_D$，我们有：

   $$V_D(L_0,L_1,L_?,I_?)=\min\begin{cases} V_I(L_0,L_?,I_?)=L_0+\lceil L_?/2\rceil\\ V_I(L_1,L_?,I_?)=L_1+\lceil L_?/2\rceil\\ V_I(L_0,L_1,L_?,I_?-1)\\ V_I(L_0+1,L_1,L_?-1,I_?)\\ V_I(L_0,L_1+1,L_?-1,I_?) \end{cases}$$

   也就是说，起码可以列出不等式：

   $$V_D(L_0,L_1,L_?,I_?)\le \min(L_0,L_1)+\lceil L_?/2\rceil\\ V_I(L_0,L_1,L_?,I_?)\ge \max(L_0,L_1)+\lfloor L_?/2\rfloor$$

   1. 当 $L_0\neq L_1$ 时，我们总可以证明直接定根是更优的，即，$I$ 做出别的选择不会比直接定根更优，因为：

      $$\max\{\text{other choice}\}\le \max\begin{cases} \min(L_0,L_1)+\lceil\frac{L_?}{2}\rceil\\ \min(L_0+1,L_1)+\lceil\frac{L_?-1}{2}\rceil\\ \min(L_0,L_1+1)+\lceil\frac{L_?-1}{2}\rceil\\ \end{cases}$$

      简单讨论就可以知道不会更优，所以一定会直接定根，即 $V_I(L_0,L_1,L_?,I_?)=\max(L_0,L_1)+\lfloor L_?/2\rfloor$，同理 $V_D(L_0,L_1,L_?,I_?)=\min(L_0,L_1)+\lceil L_?/2\rceil$

   2. 当 $L_0=L_1=L$ 时，不难发现如果使用了上面五行情况的最后两行，对面是可以直接套用我们得出的公式的，写出来化简后会发现前两行的值和后两行的值完全相等，所以此时的状态只剩下了 $I_?$ 一种，即：

      $$\begin{aligned} V_I(I_?)&=\max\{L+\lfloor L_?/2\rfloor,V_D(I_?-1)\}\\ V_D(I_?)&=\min\{L+\lceil L_?/2\rceil,V_I(I_?-1)\} \end{aligned}$$

      关键点其实就是要看我们能不能逼迫 $V_D$ 给出 $L+\lceil L_?/2\rceil$，容易发现这只与 $I_?$ 的奇偶性有关，证明可以用数学归纳法，所以双方能拿 $I_?$ 会尽可能地拿 $I_?$。

[CF1404B] Tree Tag

首先，我们来证明一个树上的结论：$\min_u(\max _vd(u,v))=\lceil D/2\rceil$，其中 $D=\max_u(\max_v d(u,v))$。

为什么？我们首先来构造出一个 $\max_v d(u,v)=\lceil D/2\rceil$ 的情况，接下来我们证明不能比它更小。

1. 令 $a,b$ 是某个直径的两个端点，我们只需要 $a,b$ 的中点作为 $u$，即可使得 $\max_v d(u,v)=\lceil D/2\rceil$，于是 $\min_u \max_v d(u,v)\le \lceil D/2\rceil$。

2. 如果存在一个 $u$，使得 $\max_v d(u,v)<\lceil D/2\rceil$，那么我们考虑任意一个直径的两个端点 $(a,b)$，会有 $d(u,a)+d(u,b)\le 2\lceil D/2\rceil-2$，根据三角不等式，我们有 $d(a,b)\le d(u,a)+d(u,b)\le 2\lceil D/2\rceil-2$。

   • 如果 $D$ 是偶数，那么 $d(a,b)\le 2\cfrac{D}{2}-2=D-2$，矛盾；
   • 如果 $D$ 是奇数，那么 $d(a,b)\le 2\cfrac{D+1}{2}-2=D-1$，矛盾。

   因此这样的 $u$ 不可能存在，所以 $\min_u \max_v d(u,v)=\lceil D/2\rceil$。

然后我们来看这道题目，考虑如下几种特殊的情况：

1. 如果一开始 $d(a,b)\le d_a$，那么一步就可以抓住；

2. 如果存在一个点 $u$，使得 $\max_v d(u,v)\le d_a$，那么只要把 $a$ 移动到 $u$ 就可以抓住，根据前文的讨论，这等价于 $\min_u\max_v d(u,v)=\lceil D/2\rceil\le d_a$；

3. 否则，无论 $a$ 跳到哪里，总会存在一个点 $v$ 使得 $d(u,v)>d_a$，即 $a$ 够不到，此时只要能保证 $b$ 总是能跳到这样的点上，就永远抓不住 $b$。

   怎么判断 $b$ 总是能够跳到这样的点上？我们不妨把每次的 $a$ 看作根，那么最坏的情况下，$b$ 需要先跳到根，再跳到这样的节点上，那么这一次的跳跃需要的 $d_b>2d_a$。

   如果满足 $d_b>2d_a$，我们就总能逃脱 $a$ 的攻击范围；否则，每一次以 $a$ 为根建树时，$b$ 都不能跳到上面 $d_a$ 层中去，我们只需要让 $a$ 步步紧逼 $b$ 总能把 $b$ 逼到它不得不向根跳的情况。

[CF1383B] GameGame

无论他们如何选择，我们能够确定的是两人得分 $X,Y$ 的异或和 $X\oplus Y=S$ 是一个定值，当 $S=0$ 时，一定是平局。

否则，我们需要从 $S$ 的特点下手，从高位向低位看：

1. 如果 $S$ 的当前位是 $0$，说明 $X,Y$ 只能是同时为 $1$ 或 $0$；
2. 如果 $S$ 的当前位是 $1$，说明 $X,Y$ 必然有一个 $1$ 和一个 $0$。

所以我们只需要关心 $S$ 的最高的为 $1$ 的位，这一位为 $1$ 的 $a_i$ 数量为奇数，为 $0$ 的 $a_i$ 数量不确定，我们需要进行讨论。

1. 若 $0$ 的数量是偶数，
   1. 若 $1$ 的数量是 $4k+1$，先手只需要拿一个 $1$，然后模仿后手操作，就可以使得先手有 $2k+1$ 个 $1$，所以先手必胜。
   2. 若 $1$ 的数量是 $4k+3$，后手模仿先手操作，就可以逼迫先手有 $2k+2$ 个 $1$，所以先手必败。
2. 若 $0$ 的数量是奇数，
   1. 若 $1$ 的数量是 $4k+3$，先手可以拿走一个 $0$，给后手必败的局面，所以先手必胜。
   2. 若 $1$ 的数量是 $4k+1$，
      • 如果先手拿 $0$，那么给后手必胜局面，不行；
      • 如果先手拿 $1$，此时后手拿 $1$ 就会给先手必胜局面，后手拿 $0$ 先手可以再拿 $1$ 给后手必败局面，所以先手必胜。

[CF1770D] Koxia and Game

由于每一个位置只有三个元素，不妨讨论互不相同元素的个数：

1. 若有超过两个元素相同，那么 Koxia 可以逼迫 Mahiru 选择这个元素；
2. 若所有元素互不相同，则 Mahiru 在这个位置至少有两种不同的选择。

如果存在一个位置所有元素互不相同，Mahiru 有 $x,y$ 两种选择，那么如果 Koxia 可以逼迫 Mahiru 选择 $\{1,2,\dots,n\} -\{x\}$，那么存在一个位置有两个 $y$，Mahiru 只要在这一步选择时选 $y$ 即可。

补充：如果前面已经选了 $y$，Mahiru 这一步选 $y$ 已经胜利；如果后面

所以 Koxia 必须每一次操作都剩下两个相同的元素，所以我们对 $a,b$ 分情况讨论：

1. 如果 $a_i=b_i$，那么这里一定会让他选择 $a_i$，所以 $c_i$ 的取值是任意的；
2. 如果 $a_i\neq b_i$，既然这里是二选一，这种问题可以映射到给一个无向图的边定方向。

最终能够成一个排列，等价于每一个点的入度为 $1$，那么既然这个图 $n$ 个点 $n$ 条边，这个图必须构成基环树森林。

对于无向边，细节少的处理方式是用并查集来做，每一个点都必须在一个有且仅有一个环的连通块中，这是容易维护的。

对于一个普通的环，答案是乘 $2$；自环乘 $n$，因为 $c_i$ 的选择无关紧要。

[CF2207D] Boxed Like a Fish

首先考虑是一条链的情况，手推不难发现，如果两端的叶子距离 $\le k+1$，则 Cyndaquil 胜，否则 Cyndaquil 败。

推广到一般情况，我们首先找到所有的叶子，把它们涂黑，然后我们可以重复下面的步骤：枚举所有的黑色点对，如果它们之间的距离 $\le k+1$，则把这一整条路径都涂黑。

这个复杂度预估一下是 $O(n^3)$，显然是错误的，但是它的正确性是没有毛病的：链的结论告诉我们，只要两个叶子距离 $\le k+1$，那么这条路径上的所有点都是必胜点；进一步地，只要两个必胜点之间的距离 $\le k+1$，那么这条新路径上的所有点也是必胜点。

基于这个思想，我们可以考虑进行树上 DP。

我们以 $v$ 为根建树，设 $T_u$ 是节点 $u$ 对应的子树，设 $dp_u$ 表示在 $T_u$ 中 $u$ 到最近黑色节点的距离，初始化叶子结点 $dp_{leaf}=0$，然后对于中间节点 $u$ 来说，如果它在 $T_u$ 中的黑色节点，那么应当存在一条跨过它的由黑色节点构成的长度 $\le k+1$ 的路径，这对应着 $dp_{c_1}+dp_{c_2}+2\le k+1$，其中 $c_1,c_2$ 是 $u$ 的子节点中 $dp$ 值最小的两个点；否则，黑色节点应当在 $u$ 的子树中，即 $dp_{c_1}+1$。