【VP 记录】ABC249

KSCD_ · 2024-06-04 19:50:37 · 个人记录

记录

ABCD 15min 切掉了，E 题思考了较长时间，中途还换过思路，60min 切掉了，F 题一直在想数据结构，没有想出正解。

VP 后补了 F，G 紫 H 黑决定不补了。

基本判断 + 数学题，略过不表。

开桶 + 记录是否有大小写，略过不表。

状压，枚举每一种选择方案，再统计出现次数恰为 K 的字母个数取最大值，时间复杂度 O(2^n\times26n))

注意到值域较小，考虑开桶。

之后枚举每个数作为 A_k，再枚举 A_j 来确定 A_i，乘法原理统计答案。复杂度为 O(A_i\sum_{k=1}^{A_i}\frac{n}{k})，调和级数也即 O(A_i\ln A_i)

前缀和优化组合计数类 dp。

首先想到设 f_{i,j} 表示长度为 i 的字符串，转化后长度为 j 的方案数，转移时枚举 k 为最后一段的长度，从 f_{i-k,j-(l_{k}+1)} 转移过来，同时要乘上与上一段字母不同的 25 种方案，时间复杂度 O(n^3)

考虑优化转移，发现所有位数相同的 l_k 均相等，也即会从第二维相等的一段连续区间转移来。因此维护前缀和数组 g_{i,j}=\sum_{k=1}^{i}f_{i,j}，分为不同位数的数统一转移过来即可，时间复杂度优化到 O(n^2)

场上想到了枚举每个修改操作为最后一次修改，再从后面的加操作中选取若干个贡献。

因此考虑倒序处理，若为修改就记录一下答案，接着消耗一次跳过来保证这次不会修改，再继续向前寻找，直到次数耗尽。加操作中，若加的是非负数，加上一定不劣，而若是负数则先放到一个大根堆中，次数用尽时先从堆中拿出最大元素加上，来换取一次跳过，直到堆也空时才是真正耗尽了次数。

其实大根堆维护的类似于反悔操作，也即把已经跳过的再选回去来节省次数。