Searching For Hope (easy) 题解

· · 题解

算法 1

输出每个点子树大小。

显然对链是正确的，期望得分 11。

算法 2

当然你也可以使用其他暴力做法。期望得分 27。结合算法 1 期望得分 38。 ## 算法 3 结论：先手全扔正电球，后手尽量让球与目标位置的 LCA 靠上。 证明： 首先，一个容量为 $c$ 的点可以被替换成一条长度为 $c$ 的链。于是接下来只考虑容量为 $1$ 的情况。 考虑对任意树归纳。归纳边界： - 任意树，目标点为根时成立。 - 大小为 1 的树，目标点是任意点时成立。 下假设对于任意大小 $\leq S$ 的树，目标点为任意点时成立。 考虑一棵大小为 $S+1$ 的树，不妨假设目标点在左侧，左侧在双方均执行最优策略时需要投下 $k$ 个球（也就是说，投下 $<k$ 个球时，无论球的电性，均无法达到目标；而由归纳假设，投下 $k$ 个正电球可以达到目标）。设右侧子树大小为 $s$。同样执行上述策略时，显然 A 投下 $\min\{2k,s+k\}$ 个球可达到目标。下证明 A 不能使用更少的球数达到这个目标。 考虑 A 依次投下的球。考虑分组：第一个球和第二个球为一组，第三个球和第四个球为一组，以此类推。不难发现，在两侧均不满且任意一组球的第一个球投下之前，根的两侧电荷一定平衡。从而 B 只能在两侧均不满时决策一组球中的第一个球。 分类讨论： - 如果两个球电性相同，无论扔哪边都得往左边掉一个，所以先扔右边。 - 如果两个球电性不同，扔右边就都去右边，扔左边就都去左边，所以扔右边。 因此，只要两侧均不满，对于任意一组中的两个球，B 一定能够保证只有后投下的球落入左侧，或者都不落入左侧。因此 A 不能使用更少的球数达到这个目标。 于是 A 最优策略得证。 证明 A 最优策略后，B 实际上已经没有决策，且过程就是让球与目标位置的 LCA 靠上。于是得证。 --- 有了这个结论以后，对于每一个点 $u$，答案可以向上递推：初始是子树大小 $a_u=S_u$，每次往上一个点，设另一个儿子的子树大小是 $S$，则 $a_u\leftarrow a_u+\min\{a_u,S\}$。 暴力递推，复杂度 $O(n^2)$，期望得分 100。