题解：P9730 [CEOI 2023] Grading Server

· · 题解

好难好难好难。

首先自己的防火墙竟然是别人操控的。好难受，我们更换一下游戏定义：

两个人，每个人有能量、金币 X_i=(A_i,B_i)。两个人轮流操作，每一轮可以选择以下两个操作之一：

  1. 让对方能量降低 A；
  2. 花费 1 金币让血量上升 S。

一个人死亡当且仅当 A+BS\leq 0。问谁赢。

容易写一个 f(A_0,B_0,A_1,B_1) 的表示谁赢。直接搜。复杂度有点抱抱抱。

【性质 1】 如果 f(X_0,X_1) 为真，那么让 A_0/B_0 增加仍未真。f(X_0,X_1) 为假那么让 A_0/B_0 减少仍然为假。

我们来说明，我们只需要关注 A_0,A_1\in(0,S) 的博弈。其余的博弈都是唯一转移的，假设现在是 0 的回合：

  1. 当 A_0\leq 0 时只能选择 2 操作；
  2. 当 A_1\geq S 时，必须选择 2。因为如果选择 2，那么对方打你你的血量会更低，而对让血量不变，违反性质 1。（【性质 2】）
  3. 当 A_0\geq S\geq A_1 时，0 必胜。因为每次 0 发动攻击 1 回血回不回来，只能乖乖挨打。
  4. 当 A_1\leq 0\leq A_0 时如果 B_0>0 就会选择 2，这时候会回到情况 2。

至此我们讨论了所有 A_0\not\in (0,S) 或者 A_1\not\in (0,S) 的情况。都是唯一转移的，而且容易快速转至 A_0,A_1\in (0,S) 的情况。

注意到 A_0+SB_0\leq V。这里直接记搜复杂度是 O(S^2\log S) 的。

能不能再给力一点！考虑 A_0,A_1\in (0,S) 的情况。如果 0 选择 2 操作，根据【性质 2】，对方必须选择打。于是我们把 1 操作变成了让自己血量上升 S-A_1 的操作。

如果 A_0+B_0(S-A_1)\geq S 了。那么我肯定先把自己的金币全买完，然后给对方致命一击。

否则，我们就会交出先手权。假设交出先手权前买了 x 次名。为了对方不能 All in 然后秒杀自己，你需要保证：

A_1-A_0'+B_1(S-A_0')<S

最终会解得 x\geq\dfrac{A_1+(B_1-1)S-A_0(B_1+1)}{(B_1+1)(S-A_1)}=k。那么我们就先买 k 次命再继续搜。状态数少了很多。

此时 (A_0,B_0,A_1,B_1) 状态数仍然很多。由于有单调性（性质 1），我们可以把一维干掉。我们尝试把 A_0 干掉，我们接下来尽可能减少 (B_0,A_1,B_1) 的状态数。

经过我们上面讨论，我们现在观察的 (A_0,B_0,A_1,B_1) 是当前你秒不掉对方，交出先手权之后对方秒不掉你。

我们观察一下什么情况对方交出先手权之后你就能秒掉对方。由于我们需要把 A_0 干掉，我们令 A_0=0。

首先假设我们第一轮买了 x 次名。此时 A'_0=x(S-A_1)。

然后第二轮对方为了制止你交回去之后把它秒了，肯定会 All in，即 A'_1=A_1-A'_0+B_1(S-A'_0)。

然后我们第三轮直接 All in，A_0''=A'_0-A'_1+(B_0-x)(S-A'_1)。

然后你要解出 A''_0\geq S 这样子就秒掉了。我们只需要 (B_0-x)(S-A'_1)\geq 2S。

展开，带上一定放缩得到 (B_0-x)x(B_1-1)(S-A_1)\geq 2S，即 B_0^2(B_1-1)(S-A_1)\geq 8S 即可。

所以如果 B_0^2(B_1-1)(S-A_1)>8S，无论 A_0 如何 0 都是必胜的。

反之，这样的 (B_0,B_1,A_1) 的个数是 \sum\dfrac{S}{i^2}\ln S 的，即 O(S\log S) 的。对每个这种对二分找出最小的 A_0 使得 0 为胜者。每次查询一个状态需要查询 map。

总的复杂度就是 O(S\log^3S+q\log S) 的。