CF1033G Chip Game 题解

· · 题解

由于 A 必胜和 B 必胜是对称的,所以 (m ^ 2 - (f + s)) / 2 即为前两问的答案,其中 fs 为后两问的答案。所以问题的关键在于求先手必胜或后手必胜的 (a, b) 对数。

有结论是把每堆石子的个数 \bmod (a + b) 后和原问题是等价的,因为如果 \bmod (a + b) 以后后手必胜,那么原局面中先手在 \ge a + b 的一堆中 -a,后手就在同一堆中 -b;如果 \bmod (a + b) 后先手必胜,那么原局面中先手先按原本的最优策略走一步,然后按上面的方法模仿后手,效果是一样的。

于是枚举 s = a + b,将 v_i \bmod s 以后排序。假设 a < ba \ge b同理)。先剔除先手后手都减不动的堆,那么满足以下两个条件中的任一个,就会使得 A 必胜或 B 必胜:

  1. 存在至少一堆使得 a \le v_i < b,这样的话有一堆石子 B 拿不到但是 A 拿得到,A 留到最后再拿可以使得 A 必胜。
  2. 存在至少两堆使得 2a \le v_i < s,这样的话 A 一定可以对一堆进行一次操作使得那一堆剩下的个数 \ge a \wedge < b,变为第一种情况。

c 表示剔除掉 < a 的石子堆以后的堆数,由于不存在情况 1, 2,所以一定是先手拿一堆。后手拿一堆。判断 c 的奇偶性,如果 c 为奇数则先手必胜,为偶数则后手必胜。

考虑知道了胜负情况后怎么计算 (a, b) 对数。由于我们算的是先手必胜或后手必胜的情况,应该剔除掉使得 A, B 必胜的 (a, b)。情况一表明,用 v_i 将数轴分段以后,a, b 一定在同一段内 (a, b \in (v_{i - 1}, v_i])。因此枚举 i,考虑计算 a, b \in (v_{i - 1}, v_i](a, b) 的对数。如果先手必胜则 a, b > \frac{v_{n - 1}}{2},因为如果有一堆石子满足 2a \le v_i < s 的话先手还是必胜。而如果后手必胜则 a, b > \frac{v_n}{2},因为 a, b 分别作为先后手总有一方会得到这一堆以后无敌。处理一下边界即可。