【做题记录】CF76

· · 个人记录

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 的答案。

最终答案即为 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)。