MOCK ??? 20221012 日志

$4$ 道题全部只会暴力。还不如直接发下来当练习做呢，省得在场上罚坐三小时浪费时间。

简略题解

A – 神灵庙

观察发现：

• 当树的形态确定时，我们总是将权值更大的节点安插到深度更小的叶子上。可以将 $a$ 降序排序后逐层填写。
• 一个节点只可能有 $0$ 个或者 $2$ 个儿子。如果只有 $1$ 个儿子，显然可将该节点删除而整棵子树全部向上平移。

设 $f(d,i,c_1,c_2)$ 表示“现在位于第 $d$ 层（此处“层”指的是节点实际深度）。已经填写好了 $a_1,a_2,\cdots,a_i$，且第 $d$ 层共 $c_1$ 个空置（非叶子）节点，第 $d-1$ 层有 $c_2$ 个此类节点”。那么两层的每一空置节点，均会有一个第 $d+1$ 层的儿子。枚举“下一层要填写 $k$ 个元素”，有转移 $$f(d+1,i+k,c_1+c_2-k,c_1)\leftarrow f(d,i,c_1,c_2)+\left(\sum_{j=i+1}^{i+k}a_j\right)(d+1)$$

考虑转化贡献：我们并行计算每个尚未填写的权值的总和。假如我们在第 $d$ 层仍未填写 $a_{i+1},\cdots,a_n$，则总和必加上 $\sum_{j=i+1}^{n}a_j$。只要在 $1\sim d$ 层填写了 $a_1,\cdots,a_i$，则不在下方层级计算它们的贡献。于是状态与 $d$ 无关。存在相似转移： $$f(i+k,c_1+c_2-k,c_1)\leftarrow f(i,c_1,c_2)+\sum_{j=i+1}^{n}a_j$$

直接计算是 $\newcommand\bigO{\operatorname{O}}\bigO(n^4)$ 的，不能接受。但我们发现，记 $f(i,c_1,c_2)$ 能够转移到的所有合法状态为 $f(i’,{c_1}’,{c_2}’)$。则必然有 $c_2’=c_1,i’+c_1’=i+c_1+c_2$。又由于有 $i$ 递增的转移顺序，故而我们可对于所有 $i+c_1=s$ 且 $c_2$ 恒定的状态保存一决策集合 $g(s,c_2)$，每次转移时以常数时间调用并更新即可。

时间复杂度 $\bigO(n^3)$。

B – 辉针城

如果两子串相等，则其二者对应位置的字符相等。暴力用并查集合并相等字符，就得到 $\bigO(\alpha(n)\sum \text{len})$ 的算法。

考虑优化这个过程。若我们知晓有若干等长的（长度记为 $l$）的，下标从 $x_1,x_2,\cdots,x_k$ 开始的子串两两相等，则设定分界点 $p<l$，有长度为 $p$ 的从 $x_1,\cdots,x_k$ 开始的子串亦相等，且长度为 $l-p$ 的从 $x_1+p,\cdots,x_k+p$ 开始的子串亦相等。我们将这一关系转化称为“下放”。

那么，我们将 $l_w$ 规定为 $2^w$，$p_w$ 规定为 $2^{w-1}$，$w$ 取遍所有自然数。则题目中的每一个询问，都可以被拆分为 $\bigO(\log_2 \text{len})$ 个长度为 $l_w$ 的子串，这些子串对应位置两两相等。考虑开设 $\bigO(\log_2 n)$ 个并查集，按照 $w$ 递减的顺序依次遍历每个拆分后的子串，合并相同者并“下放”。实现时，在第 $w$ 层，对于每个元素 $x$，记其相等类的代表元素为 $y$，我们将 $x,y$ 和 $x+2^{w-1},y+2^{w-1}$ 在第 $w-1$ 层合并即可。

时间复杂度 $\bigO(\alpha(n)n\log n)$，空间可以优化到线性。

C – 绀珠传

这种转化是我抓破头都猜不出来的那种。

考虑最优方案中是否存在“交为空”的分组。若存在，则我们将所有交为空的组合并，最后一定剩余 $K-1$ 个非空组；那么，我们贪心选择前 $K-1$ 长的线段最优——显然有两条线段的交的长度不超过两线段长度最小值。

如果不存在“交为空”的分组，则将这些线段分为两类：$S,T$。若不存在线段 $[l,r]$ 的子集 $[p,q],p\geq l,q\leq r$，则将 $[l,r]$ 归入 $S$；否则归入 $T$。由此，$S$ 中则不存在两条线段的左端点相同，且按左端点递增排序时，右端点一定亦严格递增。

考虑每一组的线段来源。如果该组存在属于 $S$ 的线段，则我们称该组为“基准组”。若钦定有 $|S|\geq k\geq K-|T|$ 组基准组，则最优方案一定具有以下特征：

• 每一基准组采用的 $S$ 中线段，必然是 $S$ 按左（右）关键字排序后连续的一段；
• 若有 $T$ 中线段 $[l,r]$ 欲加入基准组，则由 $S,T$ 的定义，必然存在至少一条线段 $[p,q]\in S$，满足 $[p,q]\subseteq [l,r]$。加入 $[p,q]$ 所在的基准组，不会继续减少该基准组的实际贡献；
• 在此前提下，我们希望尽可能多地选择若干条 $T$ 中线段，将每条线段单独分为一组。事实上，我们选择的恰为 $T$ 中前 $K-k$ 长的线段。

当确定了 $S$ 的分段方案后，第二条特征将保证其贡献不减少；而第三条特征最大化了 $T$ 中线段能够做出的贡献。

于是问题转化成：将 $S$ 依序分成 $k$ 段，问每一段的交的长度之和最大为何。记有 $|S|=n,S=\{[l_1,r_1],\cdots,[l_n,r_n]\}$。若一种方案在 $t_1,t_2,\cdots,t_k\space(t_k=n)$ 处分段，则总长为 $$(r_1-l_{t_1})+(r_{t_1+1}-l_{t_2})+\cdots+(r_{t_{k-1}+1}-l_n)$$

它只有和 $t_i$ 线性相关的项，且互相独立。于是我们令权值 $w_i=-l_i+r_{i+1}$，权值和即为 $r_1-l_n+\sum_{i=1}^{k-1}w_{t_i}$。则贪心选择即可。

时间复杂度 $\bigO(n \log n)$。

D – 天空璋

最小生成树 – Boruvka 算法 – OI Wiki

我们可以轻松借助差分思想和线段树区间加操作，维护每个节点 $x=1,\cdots,n$ 往 $y=1,2,\cdots,n$ 连边的代价。

假设现在经过了若干次迭代，正进行下一次迭代的连边。我们欲求取“从每个节点 $x$ 向不属于目前连通块的点的最小边”。则在线段树上维护区间最小值，每一节点均保存两个来自不同连通块的点的连边代价，总有一个和 $x$ 所在连通块不同。并查集维护连通情况即可。

时间复杂度 $\bigO(n\log^2 n)$。