题解：CF1839E Decreasing Game

· · 题解

CF1839E Decreasing Game（*2400）

提供一个比较自然的推法。

博弈论题，从最终局面进行倒推。这是因为可以从“选择这步会发生什么”来推得该不该选择这步。也就是知道后续操作，在开头加一个操作。

后手希望最终局面全是 0。

再往前一步，若剩下一个非 0 的数，先手选了它以后，后手就败了。

若剩下两个非 0 的数，如果它们相同，经过一次操作，转化为全 0 局面；否则经过一次操作剩下一个非 0 数，后手败。

也就是若想要一些数全变为 0，最后一次必须是留下两个相同数。这就是后手目的。

考虑我们的操作，假设有选择的两数 x < y，那么变为 0 和 y-x。

这里只讨论操作时 x<y 的情况。

那么经过若干次操作以后，留下了两数一定是 a_p-\sum op_ia_i 的形式，即初始数组中某个子集的带符号和，其中 op_i\in\{-1,1\}。若后手目的能够达到，把 x=y 方程左右两边做移项，得到一个 \sum_{i\in S}a_i=\sum_{i\in T}a_i 的形式，也就是把 a_i 划分成两个不交的集合 S 和 T，和相等。

若操作过程中涉及到了 x=y，且剩余数还未全变成 0，容易归纳转化成上面的问题。

因此后手必胜等价于可以把 a_i 划分成两个不交的集合 S 和 T，使得和相等。

必要性显然。

定策略。

若先手必胜，后手不管怎么选都达不到目的，所以直接随便选。

若后手必胜，在开始前找好划分的集合 S 和 T。最终希望 x-y=0 时，S 里的数符号和 T 里的数符号是相反的，只需要让每一步的时候，选择一个 S 里的数和一个 T 里的数。

由于两边减少量相同，和永远相同，一定可行。

这也就证明了充分性。

对于官解和题解区的做法，利用了减小的两数相等，推出和相等，因此存在等和划分，再严谨证明，很妙！

code