Day 7 讲义：阶段模拟 1——字符串维护、括号构造与线性 DP

这是一套把 Day1-Day6 的模型放在同一张卷子里的训练。做题时先给每题贴标签，再决定状态和复杂度。

1. 2036C：局部修改，只重算局部

目标串是固定长度 4 的 1100。每次只改一个字符 s[p]，不会影响所有位置，只会影响包含 p 的长度 4 子串。

这些子串的起点只能是：

p-3, p-2, p-1, p

所以维护：

cnt = 当前串中 "1100" 的出现次数

修改步骤：

1. 修改前，枚举这四个起点，若原来匹配则 cnt--；
2. 改字符；
3. 修改后，再枚举这四个起点，若匹配则 cnt++；
4. cnt>0 输出 YES。

bool good(string &s, int l){
    return l >= 0 && l + 3 < (int)s.size() && s.substr(l, 4) == "1100";
}

通用信号： 查询的是固定小长度模式，修改次数很多。不要每次扫描整串，只重算会被改动影响的位置。

2. 1996C：区间能否重排，只看频次

两个等长子串经过任意重排后要相同，等价于每个字符出现次数相同。

预处理：

pre[i][c] = 前 i 个位置中字母 c 的出现次数

查询 [l,r] 时：

countS(c) = preS[r][c] - preS[l-1][c]
countT(c) = preT[r][c] - preT[l-1][c]

两个区间的最少修改次数是所有频次差绝对值之和的一半：

ans = sum(|countS(c)-countT(c)|) / 2

因为每次替换会同时让一个“多余字符”和一个“缺少字符”得到修正。

3. 1905C：后缀最大值链

要让字符串经过允许的操作变得最小，先观察哪些位置会影响字典序。只要一个字符右边有更大的字符，它通常不应留在“需要移动的关键链”里。

从右向左维护当前最大字符：

s[i] > 当前最大 -> 更新最大，i 进入链；
s[i] == 当前最大 -> i 也可进入链；
s[i] < 当前最大 -> 不进入。

得到的位置从左到右构成后缀最大值链。题目的构造只需围绕这条链操作。

这种模型常见于字典序题：

从右往左维护“未来最优能提供什么”。

4. 2233C：构造前先保住合法性

括号串删除题的第一目标不是马上最小代价，而是确保任意前缀中：

左括号数 >= 右括号数。

处理可删位置时，若当前前缀余额将变负，必须优先删除某个右括号；若余额安全，才考虑更便宜的选择。

记住构造题的两层目标：

第一层：始终满足硬约束；
第二层：在可行选择中优化代价。

5. 2222C：先把数值关系变成符号关系

中位数相关题经常不需要维护真正中位数。若要判断某个数 x 是否能成为某段中位数，可以把元素映射为：

大于等于 x -> +1
小于 x       -> -1

一段和非负，表示其中“不小于 x”的元素不少于“小于 x”的元素。原来的中位数条件就变成了区间和条件。

之后用前缀和或 DP 判断能否切出要求数量的奇数长度段。

关键步骤：

中位数/排名条件 -> +1/-1 转化 -> 前缀和或 DP。

6. 2050E：交织字符串 DP

有两条源串 a,b，目标串 c。每次可以从 a 或 b 取下一个字符，问最少修改多少字符能得到 c。

定义：

dp[i][j] = 用 a 的前 i 个字符、b 的前 j 个字符，
           拼出 c 的前 i+j 个字符的最少修改次数。

最后一个字符有两种来源：

来自 a：dp[i-1][j] + (a[i] != c[i+j])
来自 b：dp[i][j-1] + (b[j] != c[i+j])

取最小值。

dp[0][0] = 0;
for(int i = 0; i <= n; i++){
    for(int j = 0; j <= m; j++){
        int p = i + j;
        if(i < n) dp[i+1][j] = min(dp[i+1][j], dp[i][j] + (a[i] != c[p]));
        if(j < m) dp[i][j+1] = min(dp[i][j+1], dp[i][j] + (b[j] != c[p]));
    }
}

状态坐标 (i,j) 同时表示“已经从两串各取了多少字符”，这就是交织问题最自然的状态。

7. 复盘问题

1. 为什么 2036C 只检查四个起点？
2. 为什么 1996C 的频次差要除以 2？
3. 交织 DP 的目标串位置为何是 i+j？
4. 括号构造中，什么是硬约束，什么才是优化目标？

8. 本日总结

单点改动看局部，固定模式只查附近。
区间可重排看频次，字符差值配成对。
字典序常看后缀最优，中位数常转正负和。
两串交织开二维，i+j 就是目标位置。