题解：P12638 [UOI 2020] Stone Pairs

H_Kaguya · 2025-05-30 09:57:47 · 题解

依托。

我们先忽略掉 Alice 操作完之后 Bob 可以不操作直接结束这个设定，假定每次必须完成一整轮操作。
设 a_i 表示石子数为 i 的堆数。

然后我们来看一看一轮操作会造成什么影响：

1. Alice 选择大小为 x, y 的两堆，a_x \gets a_x - 2, a_y \gets a_y - 2
2. Alice 选择大小为 x, x - 1 的两堆，a_x \gets a_x - 2, a_{x - 2} \gets a_{x - 2} + 2，这里要求 a_{x - 1} \neq 0。

这里我们发现 a_i 的奇偶性不变，因此若 a_i 为奇数则可以直接把 i 的贡献统计进去。
接下来令 b_i = \lfloor \frac{a_i}{2} \rfloor，然后操作变成：

1. 选择 x, y，b_x \gets b_x - 1, b_y \gets b_y - 1。
2. 选择 x 且 a_{x - 1} \bmod 2 = 1，a_x \gets a_x - 1, a_{x - 2} \gets a_{x - 2} + 1（这个其实有点像跳棋，前面有奇数位置就可以往前跳一步）

我们先考虑只有操作 1 的情况。这部分是一个经典的结论，对此很熟悉可以跳过这一部分。

现在有 n 堆石子，每次可以从不同的两堆里面各拿走一个，求最少剩下多少。
设 S = \sum \limits _{i = 1} ^n a_i，m = \max \limits _{i = 1} ^n a_i，则我们去比较 S - m 和 m 的大小。

若 S - m < m，即每次操作都拿走最大值中的一个，取走其他所有石子之后最多的那一堆仍然有剩余。
此时答案显然为 S - 2m。

若 S - m \ge m，则答案为 S \bmod 2。
证明的话考虑直接构造方案。每次选择最大的两堆石子分别拿走一个。
若 m 是最大值且个数不超过两个，则操作之后 (S - 2) - (m - 1) \ge (m - 1) 仍然成立。
若 m 是最大值且出现超过两次，则有 S \ge 3m，操作之后只要 m > 1 就有 (S - 2) - m \ge 2m - 2 \ge m。