【VP 记录】ABC214

KSCD_ · 2024-06-08 23:05:18 · 个人记录

记录

ABCD 切得还行，就是 C 罚了一发假做法调了一会。EFG 都看了，感觉 F 最好做，然后吃饭去了回来写了 F 发现全是漏洞，改到最后也没过。

感觉这场题目质量挺高的，好好补补。

题解

A - New Generation ABC

基本判断，略过不表。

B - How many?

基本循环，略过不表。

C - Distribution

如果暴力用每颗宝石都更新一遍，时间复杂度 O(n^2)，无法通过。

考虑断环为链，变成线性 dp，发现 t_i 最小的 i 答案一定是 t_i，以这里为开头断开，答案 {ans_i}=\min(t_i,ans_{i-1}+s_{i-1})

D - Sum of Maximum Weights

容易想到计算每一条边的贡献再求和，问题在于如何求出每一条边的贡献次数。

发现一条边能贡献当且仅当路径上没有边权大于 w_i 的边，考虑按照 w_i 不降依次加边，用并查集维护连通块内点数，这样每次 u_i 连通块中每个点和 v_i连通块中每个点分别都可以使用不大于 w_i 的边连成路径，因此可以用乘法原理累加答案。

E - Packing Under Range Regulations

首先发现尽量往左放一定不劣，所以依次考虑每一位 x（实际上只需要考虑 n 个位置），每次从所有 l_i\le x 的点中找 r_i 最小的填上即可，用堆可在 O(n\log n) 内实现。

F - Substrings

场上想对了写假了，关键在去掉重复的字符串。考虑设 f_{i,j} 表示考虑前 i 位，结尾为 j 的可行 T 数量。

则 f_{i,a_i}=\sum_{j=0}^{25} f_{i-2,j}+1，也就是所有前 i-2 位的串后面接上这一位以及这一位本身。对于另外的 k 则是 f_{i,k}=f_{i-1,k}，设 g_i=\sum f_{i,j} 即可 O(1) 转移。