[QkOI#R1] Quark and Game 官方题解

· · 题解

E - Quark and Game

\text{Description}

给定 n 个二元组形如 (a_i,b_i) ，你可以进行两个操作：

  1. 对于所有 b_i>0 的二元组，执行 b_i\gets b_i-a_i，花费 p。
  2. 对于所有 b_i>0 的二元组，执行 \operatorname{Swap}(a_i,b_i)，花费 q。

求一个花费最少的操作方法，使得所有二元组的 b_i\le 0。

\text{Solution}

最优操作序列不会出现连续的交换操作。

最优操作序列一定是若干个不连续的交换操作将攻击操作划分，故我们将一个合法的操作序列写作若干个非负整数的序列，表示每次连续攻击操作包含的次数，特别地，若一开始就进行交换操作，则序列的第一位为 0。

通过辗转相除法得到的操作序列一定是在排除了连续交换操作的情况下次数最多的操作序列。

考虑将一个二元组 (a,b) 写成序列，定义如下：

  1. 当 a=b 时，终止递归。
  2. 否则，该二元组的序列是 \lfloor\frac{b-1}{a}\rfloor 的末尾接上 (b-a\lfloor\frac{b-1}{a}\rfloor,a) 的序列。

进一步地，我们得到 n 个序列，将其建 Trie。

考虑如何枚举可能的最优序列。

我们发现可以通过枚举 Trie 上的节点 pos ，它的含义是存在一个序列的 [1,dep_{pos}] 与我们所枚举的操作序列的 [1,dep_{pos}] 相等，且下一位不相等。体现在 Trie 上，就意味着我们走到了点 pos 上。

考虑下一步要进行的攻击次数 x，为了保证不相等，所以 x 不能与当前节点任意儿子相同。记 max 表示当前节点所有儿子的权值最大值，则发现当 x>max 时只需 max+1 次就能解决所有还活着的。那 x<max 时呢？我们发现此时对于权值小于 x 的点（它是一个二元组的一个操作序列的某一个位置），它被攻击 x 次后会死亡，其它活着的点，因为 x 不和他们的权值相同，所以他们还剩两下才会被攻击死，故有 a_i<b_i，交换后只需一次攻击即可。那么令 mex 是最小的正整数，且它不是任意一个儿子的权值，可以证明 mex 是比其它 x<max 的操作优的。

从而促使我们设计一个 Trie 上的 DP。初始时我们在树根，表示一个空的操作。每次我们有三种选择：

  1. 攻击 max+1 次
  2. 攻击 mex 次，交换，攻击 1 次
  3. 选择一个儿子，直接进入

这边要感性证明一个东西，我们选择一个儿子进入后，会让其它权值小于这个儿子的权值的儿子死亡，而权值大于这个儿子的儿子则会在交换后一遍攻击致死，从而我们只需关心这个儿子的子树。

显然这个做法的时间复杂度就是 Trie 的点数，但是这里由于字符集过大，我们可以用平衡树去维护儿子（当然也可以用 map，2s 时限就是给 map 开的）。考虑辗转相除得到的序列长度是 O(\log \min(a,b)) 的，故 Trie 上的点数至多为 O(n \log \min (a,b))，时间复杂度为 O(n\log n\log\min(a,b))。