本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-04 15:14:59

A. Gift

容易发现如果只有一种权值，就是最小瓶颈生成树，可以直接跑最小生成树解决。但是有两个权值 $s_i,g_i$，考虑枚举一个权值的最大值 $s$，只用 $s_i<s$ 的边跑关于 $g_i$ 的最小生成树，求出答案 $sS+gG$。

显然跑的轮数是 $m$，如果每次都直接用所有边进行 Kruskal，还有 $O(m\log m)$ 的复杂度，整体变为 $O(m^2\log m)$。但是发现每次不一定要用所有边去跑，因为若边在先前的处理中没有进入最小生成树，那么一定不会由于加边而加入。

所以每加入一条边时用上一轮最小生成树中的边加上新边跑即可，边数至多为 $n$，复杂度降为 $O(mn\log n)$。另外 $O(n\log n)$ 的瓶颈在于对边排序，但是每次只有一条新边，插入边集即可，复杂度为 $O(nm)$。

B. Mice

Sol.1 贪心

发现只有最近奶酪有两块的老鼠需要决策，如果左边那块还没有被占用或能与前面的老鼠共用就往左，否则就往右。如果离所选奶酪 $x$ 的距离与记录的最小距离 $mn_x$ 相等，或所选奶酪还没有被选就记录答案。否则要么抢不到，要么抢了另一只老鼠原来有的，答案均不会改变。

Sol.2 DP

发现一只老鼠至多对应两块奶酪，设第 $i$ 只老鼠能前往的奶酪区间为 $[l_i,r_i]$，一定有 $0\le r_i-l_i\le 1$。而且相邻两只老鼠对应的奶酪只会有一块重复，也就是 $r_{i-1}\le l_i$。那么 DP 状态设计就要考虑到重复奶酪的分配。

设 $f_{i,0/1}$ 表示前 $i$ 只老鼠中第 $i$ 只老鼠是 / 否选 $r_i$ 这个奶酪，能吃到奶酪的最多老鼠数。边界 $f_{0,0}=0$，有如下转移：

设 $k=\max(f_{i-1,0}+1,f_{i-1,1}+[r_{i-1}\ne l_i\wedge dis(i,l_i)=dis(i-1,r_{i-1})])$，也就是选 $l_i$ 的答案。

• $l_i=r_i$ 时，$f_{i,0}=-\infty,f_{i,1}=k$。
• $l_i\ne r_i$ 时，$f_{i,0}=k,f_{i,1}=\max(f_{i-1,0},f_{i-1,1})+1$。

最终答案即为 $n-\max(f_{n,0},f_{n,1})。$

C. Mutation

求方案数，总方案数有 $2^k\le4,194,304$ 种，每种都要求出总代价，显然不能硬求，可能要做到 $O(1)$ 查询。

考虑拆字符串中每对字符对所有方案的贡献，对于 $(l,r),l<r$，如果要在最终的字符串中相邻，就一定需要删掉 $[l+1,r-1]$ 中的全部字符，并且保留 $a_l,a_r$。那么就有 $\forall i\in[l+1,r-1],a_i\ne a_l$ 且 $a_i\ne a_r$。

也就是说，对于 $r=i$ 的区间，只有每个字符最后一次出现的位置 $x$ 作为 $l$ 合法，否则就有 $a_i=a_l$。同时 $x$ 还要在 $a_r$ 上一次出现之后，否则就有 $a_i=a_r$。所以能贡献的区间就只剩至多 $nk$ 个了，维护一个 $last_i$ 就能处理出这些区间。

然后考虑分别处理这些 $(l,r)$ 的贡献，状压地用 $S$ 表示 $[l+1,r-1]$ 中存在的所有字符种类，这里用 $last_j>l$ 来判断是否存在即可。那么所有包含 $S$ 的方案均有 $d_{a_l,a_r}$ 的代价，先给 $t_S$ 加上。同时 $a_l,a_r$ 不能删，所以给 $S+a_l,S+a_r$ 分别减去 $d_{a_l,a_r}$，$S+a_l+a_r$ 容斥地加上 $d_{a_l,a_r}$。这样以后做高维前缀和即可。

另外，删字母的代价可以放到 $S=2^i$ 上，在做高维前缀和时也能统计出来。时间复杂度 $O(nk+2^k)$。