题解：P6377 [PA 2010] Termites

Felix72 · 2025-04-25 09:36:29 · 题解

先把题目转化成这样：

有一个变量 s，两人按照题设中的规则取数，先手取得 x 会使得 s \larr s + x，后手取得会使 s \larr s - x，先手要使 s 最大，后手要使 s 最小，求 s。

可以发现这个题和原题本质相同，并且两人的利益有了直接冲突，这样更好分析一些。

我们分析题目的形式，是若干个双端队列加上（至多）两个栈。

先考虑一个单谷双端队列的情况（先单调不升，后单调不降），我们声称最优策略是每次取左右两边的较大值。

证明：假设一个人不这么做，那么如果另一个人不吃这套，还是坚持取最大值，你会发现结果还不如取最大值。

这样就解决了单谷的问题。继续考虑一个不是单谷的情况：a_{i - 1} < a_i > a_{i + 1}。我们声称这三个数完全等价于 a_{i - 1} + a_{i + 1} - a_i，即把这三个数替换成这一个新的数，答案不会变化。

证明：可以看出两人都想要取得更大的数 a_i。如果先手取了 a_{i - 1} 或 a_{i + 1}，相当于把取 a_i 的机会让给了后手，那么这只有可能是先手想同时取得 a_{i - 1} 和 a_{i + 1}，否则如果先手去别的地方取数，那么相当于他还是先手，但是刚刚白白亏了 a_i - a_{i - 1}/a_{i + 1} 的权值，还不如不取。

最后考虑一下前后两个栈的问题。我们把这两个栈拼成一个双端队列，中间加一个 -\infin，那么 -\infin 一定是全局最后一个被取走的，这样就和双端队列等价了。算完后把这个 -\infin 的贡献去掉即可。