本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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)$ 转移。