P9730 [CEOI2023] Grading Server 题解

· · 题解

读前提示：本篇题解较长，并且请注意先手满足的结论如果让后手满足要难得多。

网上那篇题解问题有点多。

记 n=\max{c_H,f_H,c_G,f_G}。

我们发现每一次有盾不太好处理，于是先将 c_H 减去 f_G\times S，然后每一次能够选择加上 S，最多加 f_G 次（记 f_G=f_1 称为次数，初值为 c_H=A_1 称为攻击力），c_G 同理，有 f_2,A_2。

记攻破防火墙为防守，攻击系统为进攻。

这个博弈的结束条件是次数为 0 并且攻击力 \leq 0（注意中间过程中攻击力可能 <0 ）。

这个博弈对于双方是公平的，在 dp 时可以直接通过替换先后手来避免额外记录 0/1。

我们记一个状态/局面为 (A_1,f_1,A_2,f_2)，也用这个符号表示先手必胜或必败，胜记为 1。

这个博弈每一维都有单调性，即 (A_1+1,f_1,A_2,f_2)\geq (A_1,f_1,A_2,f_2)，其余维同理。

我们记一个局面为有用的，当且仅当通过现在的分析，这个局面还没有确定最优的下一步并且没有确定这个局面的输赢。

Subtask 3

显然的结论：

在如上结论下，我们知道有用局面满足 0\leq A_1,A_2< S。

对于这个 Subtask，模拟如上过程即可，唯一的复杂度贡献是在 A_1,A_2\geq S 时的 \log V（复杂度证明就是每过两轮 A_2 会减半）。

时间复杂度 \mathcal{O}(q\log V)。

Subtask 124

对于有用局面 (A_1,f_1,A_2,f_2) 的限制除了 A_1,A_2\in[0,S)，还有什么？

我们会将 A_1,A_2 不断加 S，最后他们都会大于 0，考虑初始输入的 A'_1,A'_2，有：

A'_*-A_*=f_*\times S

因此 f_*\leq \dfrac{n}S。

至此状态数被减少到了 n^2 个，DP 预处理他们，询问在两个都 \geq S 时仍然暴力跑，时间复杂度 \mathcal{O}(n^2+q\log V)。

Subtask 5

我们通过刚刚的尝试，发现通过分析简化有用局面是一种有效的优化方式，这启发我们继续分析。

对于有用局面 (A_1,f_1,A_2,f_2)，先手有一种很暴力的策略，每次都选择防守，而根据（*3），对手只能进攻。

记 \Delta_1=S-A_2,\Delta_2=S-A_1，也就是 (A_1,f_1,A_2,f_2)\to(A_1+\Delta_1,f_1-1,A_2,f_2)，

将这个过程做 f_1 次，如果攻击力已经比 S 大，先手直接获胜。

这样的话，有用局面又多了一个限制：A_1+\Delta_1\times f_1\leq S。

同时如果先手选择进攻，后手也可以不断防守，有限制：A_2-A_1+\Delta_2\times f_2\leq S。

做一些放缩，最终有：

\Delta_1\times f_1\leq S-A_1=\Delta_2,\Delta_2\times f_2\leq 2S

这样的状态总共有 S^2\ln S 种，DP 之，可以做到 \mathcal{O}(S^2\ln S+q\log V)。

Subtask 6（与正解无关）

但是与 remark 做法有关。

还能再给力一点吗？

神奇的结论：\forall (f_1,f_2),\exist \gamma(f_1,f_2) 满足 A_2\geq \gamma(f_1,f_2) 就使用进攻，否则使用防守。

首先我们想，这个结论成立必须满足我们对于同一个 A_2 肯定使用同一个策略。

仔细想想，这其实是显然的，因为对于同一个 f_1,f_2,A_2 用进攻/防守能赢 A_1 的一定是一个后缀，选择较大的那个后缀就好了。

这样的话，记 \forall f_1,f_2 记 h_A(A_2) 为使用进攻最小满足 (A_1,f_1,A_2,f_2)=1 的 A_1，h_F(A_2) 为使用防守最小满足 (A_1,f_1,A_2,f_2)=1 的 A_2，只要证明 \delta(A_2)=h_F(A_2)-h_A(A_2) 单调递减就可以了。

然后注意到如下事实：

那么有：

h_A(A_2+1)\leq h_A(A_2)+1 h_F(A_2+1)\geq h_F(A_2)+1

两式相减，有：

h_A(A_2+1)-h_F(A_2+1)\leq h_A(A_2)-h_F(A_2)

这样，我们就证明了 \delta(A_2)=h_F(A_2)-h_A(A_2) 单调递减了。

于是我们可以预处理出 \gamma(f_1,f_2)，具体过程为二分出 h_A,h_F，然后二分出 \delta。

这里在预处理时的查询可能范围会到很大，所以预处理查询也带 log。

而且这里有一个很麻烦的事情就是说，我们查询的时候要求出最大的一个 f_1 满足 A_2\geq \gamma(f_1,f_2)（为了快速处理非有用局面）。

同时 $f_1,f_2$ 在进攻防守时的交替次数是 $\log\log$ 次，但是证明这个实在过于困难，这里就不证了，有兴趣的同学可以来补充一下。 记 $F=\max(f_1,f_2)$，时间复杂度 $\mathcal{O}((Q+F^2\log^2F)\log n\log\log n)$。 ## Subtask 7 还能再再给力一点吗？ 在刚才的简化中我们使用了很笨的一直防守，如果进攻呢？ 一次进攻后手可能有很多种选择，只有当后手攻击力 $\leq$ 才能确定选择。 那么我们先防守 $x$ 次蓄力，然后发动攻击（$x$ 未知）。 此时还是无法确定后手的选择，但我们目的是降低后手的攻击力，提升 $\Delta_1$，然后进一步防守到攻击力大于 $S$。 后手有很多做法，不过可以规约为防守若干次（此时先手只能进攻）然后发动进攻，这样先手可以进行防守了。 无论怎么做，后手的攻击力不会超过 $A_2-(A_1+\Delta_1x)+f_2(S-(A_1+\Delta_1x))$。 同时我们发现前面还有 $A_2-A_1+\Delta_2\times f_2\leq S$ 的限制，因此： $$A'_2=A_2-(A_1+\Delta_1x)+f_2(S-(A_1+\Delta_1x))$$ $$=A_2-A_1-(f_2+1)\Delta_1x+f_2\Delta_2$$ $$\leq S-(f_2+1)\Delta_1x$$ 这可太好了！有 $\Delta'_1\geq (f_2+1)\Delta_1x$。 我们把 $\Delta'_1$ 增加了一个量级，但也付出了相应的代价：被后手攻击了一次（放成 $S$）。 再防守 $f_1-x$ 次就可以使攻击力至少变为 $(f_2+1)\Delta_1x(f_1-x)$，这个值如果超过 $2S$ 先手就可以直接获胜。 此时，我们令 $x=\dfrac{f_1}2$，就有： $$\dfrac{1}4(f_2+1)\Delta_1f_1^2\leq 2S$$ $$(f_2+1)\Delta_1f_1^2\leq 8S$$ 首先因为 0/1 状态的单调性可以把 $\Delta_2$ 记进状态。 然后 $f_1,\Delta_1,f_2$ 有多少种呢？ $$\sum\limits_{f_1=1}^D\dfrac{2S}{f_1^2}\ln\dfrac{2S}{f_1^2}$$ 用积分近似或者用 $\sum\dfrac1{i^2}=\dfrac{\pi^2}{6}$ 都可以证明这个式子是 $\mathcal{O}(S\ln S)$ 的。 时间复杂度 $\mathcal{O}(S\log^2 S+q\log S)$。 ## Remark（Subtask Extra）（与正解无关） 还能再再再给力一点吗？ 我们考虑将 Subtask6&7 的做法结合。 我们由 Sub6 知道，如果 $f_1,f_2$ 的可能性很小就好了。 我们的式子是 $(f_2+1)\Delta_1f_1^2\leq 8S$，那么，$\Delta_1$ 和 $f_2$，何如？ 这个我们好像不知道，因为 $f_2$ 是对手的次数。 那么，假设现在先手乱防一通之后进入了一个有用的局面，之后发动进攻，这个时候后手有 $(f_1+1)\Delta_2f_2^2\leq 8S$。 这不就可以了吗，因为当前局面有用，所以 $\Delta_1\times f_1\leq \Delta_2$（Subtask 5 的结论），这样就有 $(f_1f_2)^2\leq 8S$ 了！ 对于查询，我们直接枚举先手防守次数，这是 $\mathcal{O}(\sqrt{S})$ 的。 总时间复杂度 $\mathcal{O}((\log^2 S+q)\sqrt{S}\log S\log\log S)$。 ## Conclusion（与正解无关） Extra 做法有点太 shaber 了，$q$ 沦落至和 $\log^2S$ 同级。 可以考虑设 $V$，对于 $f_2\leq V$ 我们求出所有的 $\gamma(f_1,f_2)$。 此时预处理时间复杂度为 $\sqrt{SV}\log^2S\log S\log\log S$。 然后查询时，如果 $f_2> V$ 我们才枚举防守次数，时间复杂度 $q\sqrt{\dfrac{S}V}\log S\log\log S$。 平衡一下，最后时间复杂度 $\mathcal{O}(\sqrt{qS}\log^2 S\log\log S)$。 这样的话，能做的范围会稍微大一点，同时 $q$ 和 $S$ 也能贴贴了！ [再把代码放进来就装不下了](https://www.luogu.com.cn/paste/hurj8hj8)