[CF 1943E2]MEX Game 2 题解

· · 题解

题目大意

有一个序列 a 和一个初始为空的序列 c。序列 a 用 f_i 表示，f_i 表示 a 中 i 的数量，a 的最大值为 m。原题中的 Alice 和 Bob 在下文分别称为 A 和 B。

每回合 A 先操作。直到 a 空了游戏结束，A 想让 c 最终的 MEX 最大，B 想让 c 最终的 MEX 最小。求 c 最终的 MEX。

Easy Version

我们可以进行二分答案，二分 x，假设序列 a 只有小于等于 x 的数，算出最终的 MEX 可不可以到达 x + 1。找出符合条件的最大的 x，答案为 x + 1。

我们现在的任务是判断假设的 a 出现的数是否在 c 都能出现。那么 A 想的是把每种数都有一个加入到 c，B 想的是让 c 不存在一种数（只要一种就可以）。

注意：下文中所有操作都是针对没在 c 中出现的数。定义一个序列 F，F 中每个数代表每个没在 c 出现的数在 a 中的数量。

A 的策略很显然。A 每次操作在 a 中数量最少的数。

比如目前 F=[2,3,4,5]。如果选数量为 2 的数，那么 F=[3,4,5]。如果选数量为 3 的数，那么 F=[2,4,5]。第二种操作后的 F 更容易让 B 把其中的一种数删完。

说完 A 的策略，接下来说 B 的策略。B 要在 A 之前删完一种数，那么他就要有要删的目标（也就是说他最终要把一种数全删完，这个过程中主要针对它删除）。

居然 B 已经有了目标，那么 B 肯定要去删它，但不是疯狂的瞎删。比如 F=[6,8,9,10]，k=5，B 的目标是删数量为 9 的数，如果它一开始就使劲删，那么 F=[6,8,4,10]，接下来 A 第一个就选择 B 的目标。

那么很显然了，B 不要一下就把目标全删，要先把数量比它小的删一些，这样目标就不会一下在就被 A 选中了。那么 B 的策略为如果目前有其它数的数量和目标的数量相同，那么先删和目标数量相同的数，再删目标。

那么想计算就很简单了，对此时每个目标都枚举一遍即可，不过要加入一些简便的方法优化一下。单次判断时间复杂度 O(m^3)。总时间复杂度 O(m^3\log_2n)。

Hard Version

这个算法的瓶颈在于单次判断。

下面举个例子方便读者理解，k=5,F=[3,4,6,7,9]，B 的目标是最后一个数。

\begin{aligned} &F=[3,4,6,7,9]\\ A:&F=[4,6,7,9]\\ B:&F=[4,6,6,7]\\ A:&F=[6,6,7]\\ B:&F=[5,5,6]\\ A:&F=[5,6]\\ B:&F=[4,4]\\ A:&F=[4]\\ B:&F=[3]\\ \end{aligned}

可以很容易发现 B 操作过的 F 区域数值极差小于等于 1。可以算出 F 的极差小于等于 1 的最早时刻，很容易知道这个时刻之前 A 和 B 操作的区域不重合，那么用二分算即可。

假设这个时刻 F 有 n 个数，F 的和为 s。如果确定 n 和 s 的值，那么 F 的状态唯一。那么可以用 (n,s) 表示 F 的状态。如果 (n,s) 时，A 可以完成他的任务，那么当 (n,s+1) 也可以。算出 F 有 n 个数时，可以让 A 完成任务的 s 的最小值。那么就可以轻松判断 (n,s) 是否可以让 A 完成任务。

设 p_i 为当 F 有 i 个数时，可以让 A 完成任务的 s 的最小值。当 (n,s) 时，F 下一个状态就是 (n-1,s-k-\lfloor \frac{s}{n} \rfloor)。当算完 p_{i-1} 时二分出符合条件 p_i 就可以。

时间复杂度是 O(m\log_2^2m)。