Remove and Decrease Game 题解

· · 题解

下文的推导中默认 a_i 已按降序排列。

SubTask 1

起到了帮助选手理解题意的作用。

首先若 n = 1 则先手必胜。

因此当 n = 2 时移除第二堆石子的玩家输掉游戏，那么此时两位玩家均不会进行第二种操作，否则会直接输掉游戏。因此此时两位玩家会轮流进行第一种操作，直到第二堆石子被移除。显然获胜的玩家和第二堆石子数量 a_2 的奇偶性有关。我们有：当 a_2 为偶数时，Alice 获胜；否则 Bob 获胜。

SubTask 2

不难发现在 a_i 按降序排列后游戏的任何时刻场上剩余的 a 序列均为原序列的一个前缀全局删去某个数后形成的。因此不妨设 f_{i, j} 表示当场上剩余的 a 序列为原序列的前缀 i 的所有元素均减去 j 后得到的时先手是否必胜。枚举两种操作之后的局面即可实现转移，复杂度为 \mathcal{O}(nV)，其中 V = \max\limits_{2 \le i \le n} a_i。

SubTask 3

此子任务和子任务 2 的区别在于值域，因此我们考虑值域过大时对于答案的影响。我们不妨猜测当值域过大时我们可以通过某种方式将值域控制在 \mathcal{O}(n)。这里先给出结论，在 SubTask 5 的题解中会给出详细证明。我们有结论：若 a_i - a_{i + 1} > 3 ，那么我们可以进行 a_i \leftarrow a_i - 2 直至 a_i - a_{i + 1} \le 3。进而我们将值域控制在了 \mathcal{O}(n)，使用 SubTask 2 的做法即可。

SubTask 4 & 5

正解部分。

首先我们可以得出石子堆被删除的顺序一定是石子数量少的先被删除，同时通过 SubTask 1 的分析可以得出删除石子数量次大的一堆的玩家一定会输。进而我们不妨直接移除数量最多的石子堆，进而游戏转化为了第一个不能操作的人可以取得胜利。

可以发现，在大多数情况下，两种操作可以被执行的次数是一定的，具体的，第一种操作大多数情况下会被执行 a_1 次，同时第二种操作大多数情况下会被执行 n - 1 次。注意在这里及以后的分析中已经移除的数量最多的石子堆，即 n \leftarrow n - 1, a_i \leftarrow a_{i + 1}。不难发现若两种操作可以被执行的次数是确定的，那么通过其和的奇偶性即可判断出胜方。

但是若当前石子数量最小的一堆数量为 1，那么操作方可以通过进行一次第一种操作使得该石子堆被移除，同时第二种操作的可执行次数减少一次，进而改变了其和的奇偶性。可以发现在 SubTask 4 的限制下若一方希望达成此操作那么需要双方连续操作大约 10^8 次第一种操作才可以使得当前石子数量最小的一堆数量为 1，这显然是不可能的，因此在 SubTask 4 的限制下无需考虑此种特殊情况。

让我们继续分析上述特殊操作的达成条件，若某一方希望对某堆石子达成此操作以改变操作数量奇偶性，设该堆石子数量为 w，那么双方需要连续操作 w 次第一种操作，同时该堆石子不能是仅剩的一堆石子。可以发现当 w \ge 2 时一定不可能达成此操作。因此某一方可以达成上述操作必须满足当前石子数量最小的一堆石子数量为 1。而这种情况只会在游戏刚开始时出现。

但是若石子数量次小的一堆石子数量为 2，那么当前玩家完成上述特殊操作后另一方操作前也满足石子数量最小的一堆石子数量为 1，其也可以继续进行上述特殊操作。

进而我们可以证明 SubTask 3 中提到的结论：若 a_i - a_{i + 1} = 1，那么其意味着对第 i 堆石子进行特殊操作后可以继续对第 i + 1 堆操作进行。反之特殊操作的可行性不会传递，因此仅有其奇偶性影响胜负。

同时先手会进行特殊操作当且仅当当前操作数量奇偶性对其为劣势，那么在其操作后的操作数量奇偶性一定对后手为劣势，此时若后手可以继续执行上述特殊操作那么一定会执行。

因此我们可以得出，双方在进行上述特殊操作时的策略为只要上一名玩家执行了特殊操作，那么便一直尽可能地执行下去直至不能执行为止。进而我们可以得出双方对于该特殊操作会进行的轮数。进而可以判断这种特殊操作对总计操作数奇偶性的影响。

不难发现是否进行特殊操作的决定权在先手，因此特殊操作一定会对 Alice 有利，具体的，若在不考虑特殊操作的情况下 Alice 必败且特殊操作可以进行奇数轮，那么 Alice 可以进行特殊操作进而取得胜利。

综上，我们得到了先手必胜的充要条件：不考虑特殊情况下其必胜或特殊操作可以进行的轮数为奇数。

时间复杂度为 \mathcal{O}(\sum n \log n)，瓶颈在于排序。