继续刷 CSP-S 2023 真题。这题考点是线性动态规划，先把题意吃透。
题目来源：ACGO A7096 ｜ 洛谷 P9753
难度定位：提高+/省选- ｜ 通过率：34.09%
一、题目信息
题目名称：消消乐
所属赛事：2023 年 CSP-S 组复赛
官方难度：提高+/省选-
涉及知识点：线性动态规划
题目链接：https://www.acgo.cn/problemset/info/7096
洛谷编号：P9753（同一道题，两个平台均可提交，代码通用）
坑点（这题失分基本都在这）
- 状态定义要写清楚，最好注释在代码里
- 遍历顺序错了会用到本层刚更新的值，结果就偏了
- 多阶段 DP 每进入新阶段，之前的数组要重新初始化
- 高难度题的暴力分很关键，先写一版能过的部分分再想正解
题意简述
用一句话概括：
小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两
个相邻的元素。
现在，他有一个长度为 n 且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。
其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。
小 L 想知道，这个字符串的所有非空连续子串中，有多少个是可消除的。
前置知识
先把这题需要的基础理一遍，熟悉的可以直接跳到思路部分。
状态 + 转移
DP 三步：定义状态 f[i] 表示什么；写转移方程 f[i] = ...；确定初始值和遍历顺序。初学者最容易错在状态定义太模糊。
二、思路分析
在 CSP-S 2023 里属于提高+/省选-档，考场上建议放在中场，先拿暴力分做。
先说结论，再讲为什么。
题目解析
根据性质，若是s[i,j-1]与s[j,k] 均为合法子串，那么 s[i,k] 必为合法子串。
考虑 dp，设f_i表示以第 i 位作为结尾的合法子串数量，容易得出转移方程：f_i=fg_i₋₁+1，其中 g_i表示最大且能使s[g_i ,i] 成为合法子串的下标。答案即为 f_i，i从1到n累加求和。
由于g_i是满足条件中最大的，因此必有s_i=sg_i 。我们就可以从 i 往前跳，初始时 g_i=i-1，之后不断令g_i->gg_i-1，直到满足 s_i=sg_i。
但此方法会被一些特殊数据卡到n²，要考虑优化。
只需要提前记录下能成为合法子串的最大下标就可以了。
三、完整代码
#include <iostream> #include <vector> #include <cstdio> using namespace std; // CSP-S 2023 消消乐 // 长度为 n 的小写字母串。一个串「可消除」定义为：可以通过反复删除相邻的相同字符 // 最终变成空串。求所有非空连续子串中有多少个可消除。 // // 做法（栈 + 前缀哈希）： // 用栈模拟消除过程。若从前缀 i 出发、处理到 j 时栈为空，则 [i+1, j] 可消除。 // 经典技巧：对每个位置 r 记录「以 r 结尾的最短可消除后缀的左端点 lst[r]」， // 若不存在则为 0；则 ans = sum over r of (lst[r]) 【即以 r 结尾的 // 可消除子串数量 = lst[r]，因为 [1..lst[r]] 这些起点都可】。 // 维护：用「栈的哈希」判断当前栈顶状态是否在之前出现过。 // 这里给出一个 O(n^2) 的朴素实现，可以通过 n <= 5000 的部分测试点。 int main() { int n; scanf("%d", &n); string s; { // 读入整行字符串（可能很长） static char buf[1000005]; scanf("%s", buf); s = buf; } if ((int)s.size() > n) s = s.substr(0, n); long long ans = 0; vector<char> stk; stk.reserve(s.size() + 1); // 枚举每个起点，用栈模拟（O(n^2)，可通过 n <= 5000 的部分测试点） for (int i = 0; i < (int)s.size(); ++i) { stk.clear(); for (int j = i; j < (int)s.size(); ++j) { char c = s[j]; if (!stk.empty() && stk.back() == c) stk.pop_back(); else stk.push_back(c); if (stk.empty()) ++ans; } } printf("%lld\n", ans); return 0; }四、代码分段拆解
代码不长，但每一行都有讲究，分段过一遍。
头文件与全局变量
先把用到的头文件和全局变量放上来。全局变量在竞赛里很常用，好处是函数之间共享方便，代价是要小心初始化和被意外改写。
#include <iostream> #include <vector> #include <cstdio>using namespace std; int main() { int n; string s;主体逻辑
主体部分按顺序完成读入、计算、输出。main函数尽量保持线性，把复杂的逻辑拆成独立函数，出问题时更容易定位。
状态与转移
DP 部分建议在代码里写上状态含义的注释。过几天回头看，没有注释的 DP 基本读不懂。
五、实例模拟
用题目给的样例走一遍，验证我们的思路。
样例 1
输入：
8 accabccb输出：
5以第一组样例为例，输入是8、accabccb，正确输出是5。建议把这两行数据抄在纸上，用上面的代码手动走一遍，重点看循环变量怎么变化、答案在哪一步被更新。能自己推出来的东西，比看懂代码印象深得多。
六、踩坑总结
把这题的经验固化下来。
- 状态定义要写清楚，最好注释在代码里
- 遍历顺序错了会用到本层刚更新的值，结果就偏了
- 多阶段 DP 每进入新阶段，之前的数组要重新初始化
- 高难度题的暴力分很关键，先写一版能过的部分分再想正解
另外提醒一句：这题在 CSP-S 2023 里是提高+/省选-难度，考场上如果没有把握拿满分，先把暴力写法交上去拿到部分分，再回头优化。CSP 是打分制，空着不写才是最亏的。
七、知识点拓展
这题的核心是动态规划。
CSP 的 DP 题很少单独考，通常和别的知识点结合。判断能不能用 DP，就看有没有「阶段 + 状态」的结构，以及当前决策会不会影响后面的选择。
建议的练习路径：
- 先把本题独立写一遍，不看代码，遇到卡壳再看提示
- 换个平台提交（ACGO 和洛谷都试试），确保代码在两个平台都能过
- 找两到三道同类型的题练手，巩固这类问题的识别能力
八、适用人群
这题适合这些阶段的同学：
- 目标是 CSP-S 高分或省选的同学
- 想通过真题理解高难度题如何从暴力优化到正解的同学
- 想弄明白动态规划类问题标准解法的同学
有更好的写法欢迎在评论区交流，一起进步。
关于这个系列
这是「CSP 真题逐题精讲」的第 41 篇。我会按年份从 2019 一路刷到 2025，
CSP-J 和 CSP-S 全覆盖。每篇都给：双平台题号（ACGO + 洛谷）+ 逐行代码拆解 + 真实样例模拟。
跟着刷完这一套，CSP 第一轮的选择题和基础题基本就稳了。
下一篇：CSP-S 2023 密码锁（普及/提高-）
👉 关注我，不错过后续更新。评论区告诉我你现在刷到哪一年了，我看看能不能按大家的进度调整更新节奏。
