自动搬运

查看原文

来自洛谷，原作者为

	lbw 若有 笃信之物 莫忘厮守

搬运于2025-08-24 22:51:13，当前版本为作者最后更新于2024-07-09 16:37:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

记 $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

显然的结论：

• 在 $A_1\leq 0$ 时必然选择防守。（*1）

• 如果 $A_1\geq S\geq A_2$，那么先手每次选择攻击，后手攻击力只会越来越少，最终死亡。（*2）

• 如果 $A_2\geq S$，先手必然选择进攻，否则在对手进攻后会使 $A_1,f_1$ 都减小进入更劣局面。（*3）

• 如果 $A_1\geq 0\geq A_2$，先手可以通过攻击进入情况 $A_1\geq S\geq A_2$。（*4）

在如上结论下，我们知道有用局面满足 $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)$ 单调递减就可以了。

然后注意到如下事实：

• 如果使用攻击，则 $(A_1,f_1,A_2,f_2)\leq (A_1+1,f_1,A_2+1,f_2)$，证明可以考虑模拟一轮操作。
• 如果使用防守，则 $(A_1,f_1,A_2,f_2)\geq (A_1+1,f_1,A_2+1,f_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)$（为了快速处理非有用局面）。

$\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$ 也能贴贴了！

再把代码放进来就装不下了