2025 暑期模拟赛题目选记
字符替换
是洛谷 P8885 的加强版。
首先考虑字符串本质不同子序列怎么求。考虑 dp。经典的 dp 是设 \(f_i\) 表示以字符 \(i\) 结尾的本质不同子序列的个数。设 \(f_s\) 表示 \(\sum f_i\)，那么加入字符 \(c\) 后有 \(f_c\to f_s+1\)。那么在本题中我们只需要维护其奇偶性，于是手玩一下发现实际上在 \(\bmod 2\) 意义下相当于将 \(f_i,f_s\) 交换这样一个操作。
考虑对于全局询问。不难发现这样的 dp 状态数很小，考虑 ddp。令 \(g_{i,f_0,f_1,f_2,f_s,t}\) 表示前缀 \(i\) 在 \(f_{0,1,2,s}\) 状态为 \(0/1\) 时，前缀 \(i\) 好的字串个数为 \(t\)。转移就是枚举字符的形式，答案是 \(\sum g_{n,?,?,?,?,t}\)。
那第二维可以状态压缩，用线段树维护矩阵做。显然复杂度难以接受。注意到 \(m\) 较大，\(n\) 较小，考虑挂在猫树上分治，可以优化一部分复杂度。注意到 dp 时一部分矩阵可以用向量替代，于是直接维护向量即可。进一步的优化是将向量在每层猫树上从下往上递推处理来优化一部分复杂度。然后这题就做完了。
麒麟草
先考虑离线的操作。将 \(x\) 轴离散化，将 \(x_1+1\) 插入 \([y_1+1,y_2]\)，在 \(x_2+1\) 撤销 \([y_1+1,y_2]\)。对于询问，拆成 \(\text{Q}(x_2)-\text{Q}(x_1)\) 的形式。不难发现我们维护的实际上是一个区间历史版本和。维护两个标记 \(\text{hsm,hct}\) 分别表示在该节点上方无标记时该节点的历史版本和与被覆盖的次数，询问时从上到下加入答案的贡献即可。
对于在线，无法将询问的 \(x\) 轴离散化。那么先将修改的维度离散化后可持久化，询问时拆成历史部分和当前部分两类贡献相加即可。
abstract
就是说由于值域很小，位运算操作会改变一个位上的值，因此取值的个数是 \(O(\log V)\) 级别的。于是对于所有 路径，在 \(\text{LCA}\) 处暴力 \(O(\log^2V)\) 去合并路径，用 std::map 存一下状态数即可。
草莓之歌
是洛谷 P9338。
先考虑暴力的 dp。显然我们要做的是把序列划分成 \(k\) 个区间，每个区间内部有严格偏序的方案数。那么设 \(f_{i,j}\) 表示前 \(i\) 个数划分成 \(j\) 个区间的方案数，那么有 \(f_{i,j}=\min_{k=0}^{i-1}\{{f_{k,j-1}+w(k+1,i)\}}\)。其中 \(w(i,j)=\sum_{k=i}^j\max(0,c_k-i)\)，其中 \(c_k\) 表示位置 \(k\) 前方 B 的个数，对于 \(a_k=\) B，\(c_k=0\)。这样做的意义是将应该在 A 后边而实际上在这个 A 前边的 B 挪到后面来。
那这个 dp 是一个划分序列的形式啊，考虑答案呈现一个凸包的形式，于是 wqs 二分将外层削成一个 \(\log\)。考虑内层如何优化复杂度。将 \(w\) 拆开，发现这个 \(\max\) 的形式很不好处理，又注意到 \(c\) 实际上是有单调性的，于是维护一个 \(p_i\) 表示第一个 \(c_{p_i}>i\) 的位置来统计贡献，做一个前缀和的优化统计。那这是一个斜率优化的形式啊！于是总的复杂度就是 \(O(n\log n)\) 的了。