MOCK NOIP 20221014 日志

签到题看了半个小时；T2 没有考虑到只需要包含最优解即可，非要确定另一多余状态，只拿了部分分。

T3 只会考虑 “$x, y$ 的公共祖先中含有 $l$ 的概率”，不会高效计算“当二者的 $\operatorname{lca}$ 恰为 $l$ 时”的期望/概率与总长之和的乘积，仍然只有暴力分。

T4 无思路。

一句话（?）题解

A – 签到题

可以简单用归纳法证明，仅有所有管道中通行时间最大的会阻塞进度，是为两数据包到达终点的时间间隔。算出首个数据包到达的时间再将前者相加即可。

B – 简单题

第一反应是类似笛卡尔树一样，在区间上依次合并区域最大值并计算贡献。$n \leq 300$ 似乎也在暗示这是一个区间 DP。

$\text{48 pts}$ 做法

设 $f(l,r,\text{mx})$ 表示“考虑完成区间 $[l,r]$ 内所有贡献，且最大值恰好为 $\text{mx}$”的最大权值和。转移时从小到大枚举最大值 $\text{mx}=V_{i,j}$，枚举包含它的区间，尝试转移 $$f(l,r,\text{mx})\leftarrow f(l,i-1,\text{mx}’)-C_{i,j}+\text{mx}\cdot \operatorname{calc}(l,r,i)+f(i+1,r,\text{mx}”)$$，其中 $\operatorname{calc}(l,r,i)$ 计算 $\sum_{l’=l}^{i}\sum_{r’=i}^{r}Q_{l’,r’}$，可以由二维前缀和实现。稍加演算会发现，这样转移不会重复计算贡献。时间复杂度 $\operatorname{O}(\sum K_{i}N^2)$。

正解

上述转移是没办法优化的—— $\operatorname{calc}$ 函数注定会调用和 $l,r$ 均相关的数组项，难以拆分。

但注意到这是最优解问题，我们不必关注某个区间真正的最大值是多少。因此设 $f(l,r)$ 表示“所有方案下 $[l,r]$ 区间内部贡献的最大值”。转移时按区间长度顺序从短到长即可。

此种转移方式不会漏掉最优解，且不会重复计算同一区间的贡献。

证明：区间合并的过程本质上是在构建笛卡尔树，所以可以立刻得到后一结论；

但由于未保证转移顺序为“区间最值从小到大”，我们可能“错误”计算了某个区间的最大值。例如我们钦定了 $[l,r]$ 的最大值为 $a_i=\text{mx}$ 并且从两侧子区间转移，得到了 $f(l,r)$ 的最优解；如果在全局最优解中，我们确实采纳了 $V_i=\text{mx}$ ，但在 $r$ 的右侧存在一个位置 $j$，满足最优解中采纳了 $V_j,V_j<V_i$，则可以发现 $\text{mx}$ 扮演的角色不仅仅是 $\{[l’,r’],l’\in[l,i],r’\in[i,r]\}$ 中所有区间的最大值，也是 $\{[l’,r’],l’\in[l,i],r’\in{\color{red}(r,j]}\}$ 中的最大值。则若考虑 $f(L,R),L=l,R\geq j$ 的计算，如果此时钦定 $V_j$ 作为最大值，同时采纳 $f(l,r)$ 作为子区间转移结果的一部分，必然导致 $\{[l’,r’],l’\in[l,i],r’\in{\color{red}(r,j]}\}$ 最大值并非按照 $V_i$ 而是按照 $V_j$ 计算。这显然不比采纳 $V_i$ 作为 $[l,R]$ 的最大值决策点更优。故而我们不会漏掉最优解。

实际操作中不能对于每个区间 $[l,r]$ 均逐个枚举最大值并且转移。但考虑一个固定的 $i$，我们尝试转移 $f(l,r)\leftarrow f(l,i-1)+\operatorname{calc}(l,r,i)V_{i,j}-C_{i,j}+f(i+1,r)$ 时，若将 $\operatorname{calc}(l,r,i)$ 看作自变量 $x$，$V_{i,j}$ 看作斜率 $k_j$，$C_{i,j}$ 看作截距 $b_j$，则对于同一个下标的可选元素集合，能够得到若干一次函数 $l_j:y=k_jx+b_j$，我们要找到 $x=\operatorname{calc}(l,r,i)$ 时它们的最大值。这可以离线所有 $\operatorname{O}(N^3)$ 个询问并 $\operatorname{O}(\sum{K_i})$ 构建凸包，线性求解。也可以改变转移顺序，从右往左移动待转移区间左端点 $l$，实时维护每个决策点 $i$ 在每个右端点 $r$ 处计算得到的 $\operatorname{calc}(l,r,i)$，它是单调不降的。时间复杂度 $\operatorname{O}(N\sum{K_i})$。

C – 数数题

在根确定时，每个节点到根的路径长度完全是由其父亲决定的。所以记 $f(x)$ 表示 $x$ 到 $1$ 的路径上（不含两端点）经过的节点权值和的期望，记 $b_x=\sum_{y=1}^{x}a_y$，有转移 $$f(x)=\sum_{y=2}^{x-1}\frac{a_y(c_y+f(y))}{b_{x-1}}$$，则 $\operatorname{E}(\operatorname{dis}(x,1))=2f(x)+c_1+c_x$。

不难理解：$$\begin{aligned} \operatorname{E}(\operatorname{dis}(x,y))=&\operatorname{E}(\operatorname{dis}(x,1))+\operatorname{E}(\operatorname{dis}(y,1))-2\sum_{l=1}^{x-1}\operatorname{E}(\operatorname{dis}(l,1))\operatorname{P}(l \text{为} x,y \text{的}\operatorname{lca})\\ &-2\operatorname{P}(x \text{是} y \text{的祖先})\operatorname{E}(\operatorname{dis}(x,1))\quad{(x<y)} \end{aligned}$$

考虑枚举路径节点集合 $S_{1}, S_2$ 分别表示 $l,x$ 和 $l,y$ 之间的路径。若 $|S_1|=k_1+1,|S_2|=k_2+1$，深度从小到大依次为 $x_{1,0}=l,x_{1,1},\cdots,x_{1,k_1}=x$，$x_{2,0}=l,\cdots,x_{2,k_2}=y$，则出现 $S_1,S_2$ 的概率为 $$\begin{aligned} &\prod_{i=1}^{k_1}\frac{a_{x_{1,i-1}}}{b_{x_{1,i}-1}}\prod_{i=1}^{k_2}\frac{a_{x_{2,i-1}}}{b_{x_{2,i}-1}}\\ =&\frac{\prod_{i=0}^{k_1-1}a_{x_{1,i}}}{\prod_{i=1}^{k_1}b_{x_{1,i}-1}}\frac{\prod_{i=0}^{k_2-1}a_{x_{2,i}}}{\prod_{i=1}^{k_2}b_{x_{2,i}-1}}\\ =&\frac{a_{x_{1,0}}a_{x_{2,0}}}{b_{x_{1,k_1}-1}b_{x_{2,k_2}-1}}\prod_{i=1}^{k_1-1}\frac{a_{x_{1,i}}}{b_{x_{1,i}-1}}\prod_{i=1}^{k_2-1}\frac{a_{x_{2,i}}}{b_{x_{2,i}-1}}\\ =&\frac{a_l^2}{b_{x-1}b_{y-1}}\prod_{i=1}^{k_1-1}\frac{a_{x_{1,i}}}{b_{x_{1,i}-1}}\prod_{i=1}^{k_2-1}\frac{a_{x_{2,i}}}{b_{x_{2,i}-1}} \end{aligned}$$

转化后 $x,y,l$ 和中间所有节点的贡献全部独立。对所有可能的 $S_1,S_2$ 的出现概率求和，也即对于所有 $z\in(l,x)$，我们既可以放入 $S_1$，亦能放入 $S_2$，或二者皆不加入，故而在总概率和中的贡献为 $(2\cdot \frac{a_z}{b_{z-1}}+1)$；同理，$\forall z\in(x,y)$，均有权值 $\frac{a_z}{b_{z-1}}+1$。利用前缀积优化计算即可 $\operatorname{O}(n)$ 解决本题。

D – 最后一题

神仙交互/构造！

假若我们正求取 $x$ 的子树结构。记 $z_1,\cdots,z_k$ 为当前还没有求取其其子树结构的所有节点。我们可以二分一个最小的位置 $i$，表示满足 $z_{1,\cdots,i}$ 在 $x$ 的子树中（判定方法：考虑 $x$ 是否在根 $\text{rt}$ 与 $z_{1,\cdots,i}$ 构成的连通块中），此时 $z_i$ 必定在 $x$ 的子树中。将 $z_i$ 标记为“正在递归”，从上述列表中删除，然后递归求取其结构。容易发现，该过程将不重不漏地对每一个 $x$ 恰求取一遍其子树结构。

求 $x$ 的结构剩下的最后一步是判断哪些节点是 $x$ 的儿子。我们将“已经求取完成本身子树结构，并且父亲暂时未知”的节点记作 $y_1,\cdots,y_{p}$。易知在当前列表中，若 $y_i$ 在 $x$ 子树内，则他只可能是 $x$ 的儿子，否则某个在 $x$ 子树中的 $z_j$ 必然没有求取/递归完成。同样地，二分首个满足条件的 $y_i$ 的位置，将其划为 $x$ 的儿子并从列表删除。

最多进行 $\operatorname{O}(n \log n)$ 次查询。实际实现时，需注意当列表内没有满足条件的节点时，我们仍需要 $\operatorname{O}(\log n)$ 次询问判断，这是相当不划算的，无法得到满分。故而每一次找节点之前，我们用一次额外的查询询问整个列表是否都没有合法节点。