电网检修

idea, solution, std, data by GeZhiyuan

这是一个结论题。假设树高为 $h$，我们对 $h$ 分类讨论：

当 $h < k$ 时：

• 我们可以先假设 $k=n-1$ 即没有限制，然后两人在树上最终的位置分别是 $u, v$。此时不难发现两人最优情况下，相对于 $2(n-1)$ 能省去的总距离为 $u, v$ 间的距离 $d$。即我们要找到树的直径长度。
• 然后我们考虑加上 $k$ 的限制。此时两人最终距离不会超出 $k$，因此省去的距离也不能超出 $k$。我们尝试证明答案能省去的距离即为 $\min(d, k)$。
• 先找出直径两端点 $s, t$，然后不停将 $s$ 令为 $s$ 的父亲，直到 $s, t$ 距离小于等于 $k$，由于树高的限制，最终 $s$ 也不会成为 $t$ 的祖先，一定会有一时刻找到合适的 $s$。此时可以发现所有点和 $s$ 的距离都小于等于 $k$，而又有所有点和 $1$ 的距离都小于等于 $k$。因此只要先让伏特走，此时欧姆的位置一直在 $1$；再让欧姆走即，此时伏特的位置一直在 $s$。上述策略一定可以可满足题目限制。也就省去了 $\min(d, k)$ 的距离。

当 $h \geq k$ 时：

• 不难发现，此时对于子树树高大于 $k$ 的点，两人都必须经过。因为对于一个深度大于等于 $k$ 的点，当两人中的某人到达这个叶子时，另一个人必定在其 $k$ 级祖先的子树内。也就是两人都经过了这个 $k$ 级祖先。 那么这样的 $k$ 级祖先所构成的点集即为子树树高大于 $k$ 的点构成的点集。
• 假设子树树高大于 $k$ 的点构成的点集大小为 $m$。我们让两人分别去遍历整棵树，和子树树高大于 $k$ 的点构成的树。两树树高分别为 $h$ 和 $h-k$，根据经典结论相对于 $2(n-1)+2(m-1)$ 至多可以省去 $2h-k$ 的距离，并且发现可以轻松构造出一种移动策略达到这个值。此时答案即为 $2(n+m-2)-2h+k$。
• 最后我们尝试证明其他策略一定不优于 $2h-k$。即对于一种其他的遍历到的点的分配方式。首先对于子树树高大于 $k$ 的点构成的树，一定都要被两人经过的点覆盖。而相当于其他的点我们要去分配给两个人。而我们有两人最终位置距离不超过 $k$。首先对于子树树高大于 $k$ 的点构成的树，两人省去的路径长度不超其树高两倍，即不超 $2h-2k$。而对于不在这个树内省去的距离，由于两人距离不超 $k$，因此也至多省去 $k$。综省去的距离不超 $2h-k$。

于是此题就在 $O(n)$ 内得以解决。

If there exists maxdep >= k, consider the component formed by the k-th ancestors of all nodes. Volt walk through all the tree, Ohm walk through the component. The answer is: 2*(n-1)-maxdep-(maxdep-k).

Otherwise, the two people can move to two leaves within some subtree, reducing the distance by min(diameter,k). The answer is: 2*(n-1)-min(diameter,k).

电子运动

idea, solution, std, data by Rainbow_sjy

算法 I

分析电子掉出去后，最终的结构是什么。

假设电子是从左边掉出去的（如果是右边则把所有操作反一下）。

假设电子一开始放在 $i$ 位置，$[1,i]$ 中有 $x$ 个 +，$[i+1,n]$ 中有 $y$ 个 -。

若 $x\le y$，此时电子是从左边掉出去的，且 $[1,i]$ 全部变成 +，$[i+1,n]$ 中的前 $c$ 个 - 变成 +，其中 $c$ 是 $[1,i]$ 中初始的 + 个数。

枚举初始位置，枚举往右边碰到的最远位置，用组合数计算。

对于右边掉出去的情况就反过来做一遍。时间复杂度 $O(n^2)$，期望得分 $64$。

算法 II

这个模型的结构是十分对称的，可以观察更多性质。

考虑电子从左边掉出去，且最后变成全是 + 的情况，此时需要满足：$[1,i]$ 的 + 个数等于 $[i+1,n]$ 的 - 个数。我们可以发现，此时初始序列里需要恰好有 $i$ 个 - 和 $n-i$ 个 +。（这个过程类似范德蒙德卷积）

进一步，考虑 $i$ 向左的第一个 - 和向右的第一个 +，设为位置 $x$ 和 $y$。那么电子走 $i\to x\to y\to i$ 的路径，恰好交换了 $x$ 和 $y$ 的符号。

当 $[1,i]$ 全部变为 - 后，可以随意交换 $[i+1,n]$ 中的 +。

通过等价交换之后，可以把字符串看作一个前缀全是 -，一个后缀全是 +。于是我们可以发现一个神奇的结论：字符串是否等价只和其中 + 的总个数相关。

进一步讨论可以得到：初始位置是 $i$，有 $\ge n-i+1$ 个 +，则会减少 $n-i$ 个 +；否则会增加 $i$ 个 +。

那么对于初始位置是 $i$，初始有 $j$ 个 +，则最终会有 $(i+j) \bmod (n+1)$ 个 +。于是用一次卷积即可解决问题，时间复杂度 $O(n\log n)$，期望得分 $100$。

电阻匹配

idea, solution, std, data by Kubic

算法 I

考虑 kth-minmax 容斥：

$$ \operatorname{kthmin}(S,k)=\sum\limits_{T\subseteq S,|T|\ge k}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\max(T) $$

转化为对于每个 $k$ 求出如下问题的答案；

• 先将 $a_{1\dots 2n}$ 两两匹配，一对匹配的权值为两个元素之和。然后在 $n$ 对匹配中选出恰好 $k$ 对，一组方案的权值为选出的匹配的最大权值。求所有方案的权值和。

设 $V$ 为一个足够大的值。则有：

$$ \max(S)=V-\sum_{w=0}^{V-1}\prod_{i\in S} [i\le w] $$

考虑枚举 $w$ 计算这个 $w$ 对答案的贡献。可以发现本质不同的 $w$ 只有 $O(n^2)$ 种。

我们将数分为 $\le\dfrac{w}{2}$ 和 $>\dfrac{w}{2}$ 两种，分别设为序列 $p,q$。

我们需要关注选出恰好 $k$ 对 $\le w$ 的匹配的方案数，剩余的 $n-k$ 对匹配可以在剩余的 $2(n-k)$ 个元素之间任意进行，方案数容易计算。

不妨设 $p$ 不降，$q$ 不增。

显然一个 $q$ 中的元素能匹配的一定是 $p$ 的一段前缀，而 $p$ 中的元素之间可以任意匹配。

设 $r_i$ 表示最大的数满足 $p_{r_i}+q_i\le w$。

设 $f_{i,j}$ 表示考虑 $q_{1\dots i}$，其中共进行了 $j$ 对 $p,q$ 间的匹配的方案数。

显然有转移方程:

$$ f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times (r_i-j+1) $$

设从 $i$ 个数种任意选出 $j$ 对匹配的方案数为 $c_{i,j}$。显然有：

$$ c_{i,j}=\dfrac{i!}{j!(i-2j)!2^j} $$

则一个 $w$ 对答案的贡献为：

$$ \sum f_{|p|,i}\times c_{|q|-i,k-i} $$

这两部分的时间复杂度均为 $O(n^2)$，而我们需要对每个 $w$ 做一遍。于是我们得到了一个总时间复杂度 $O(n^4)$ 的算法。

算法 II

考虑优化上述算法。

可以发现，第二部分中我们可以将 $|q|$ 相同的 $w$ 对应的 $f$ 放到一起计算贡献，而一共只有 $O(n)$ 种不同的 $|q|$。因此这一部分的时间复杂度容易优化到 $O(n^3)$。

现在的瓶颈在于对每个 $w$ 计算 $f$。

设 $g_{i,j}=f_{i,i-j},G_i(x)=\sum g_{i,j}x^j$。则有：

$$ g_{i,j}=g_{i-1,j-1}+g_{i-1,j}\times(r_i-i+j+1) $$

$$ G_i(x)=(x+r_i-i+1)G_{i-1}(x)+xG'_{i-1}(x) $$

设 $H_i(x)=e^xG_i(x)$。则有：

$$ H_i(x)=(r_i-i+1)H_{i-1}(x)+xH'_{i-1}(x) $$

$$ [x^j]H_i(x)=(r_i-i+j+1)[x^j]H_{i-1}(x) $$

因此我们可以在 $O(n)$ 的时间复杂度内计算出 $H_{|p|}(x)$。

但是通过 $H_{|p|}(x)$ 得到 $f_{|p|,*}$ 是 $O(n^2)$ 的，我们不能对于每个 $w$ 都进行处理。

与之前类似地，对于 $|q|$ 相同的 $w$，我们可以先将它们对应的 $H_{|p|}(x)$ 叠加起来得到 $H(x)$，然后计算 $G(x)=\dfrac{H(x)}{e^x}$，进一步得到 $f_{|p|,*}$ 叠加的结果。

这样我们就能在 $O(n^3)$ 的时间复杂度内得到转化后问题的答案。