【VP 记录】ABC249

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

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

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

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