2023信奥赛C++提高组csp-s复赛真题及题解：消消乐
题目描述
小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两个相邻的元素。
现在，他有一个长度为n nn且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。
其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。
小 L 想知道，这个字符串的所有非空连续子串中，有多少个是可消除的。
输入格式
输入的第一行包含一个正整数n nn，表示字符串的长度。
输入的第二行包含一个长度为n nn且仅由小写字母构成的的字符串，表示题目中询问的字符串。
输出格式
输出一行包含一个整数，表示题目询问的答案。
输入输出样例 1
输入 1
8 accabccb输出 1
5说明/提示
【样例 1 解释】
一共有5 55个可消除的连续子串，分别是cc、acca、cc、bccb、accabccb。
【数据范围】
对于所有测试数据有：1 ≤ n ≤ 2 × 10 6 1 \le n \le 2 \times 10^61≤n≤2×106，且询问的字符串仅由小写字母构成。
| 测试点 | n ≤ n\leqn≤ | 特殊性质 |
|---|---|---|
| 1 ∼ 5 1\sim 51∼5 | 10 1010 | 无 |
| 6 ∼ 7 6\sim 76∼7 | 800 800800 | 无 |
| 8 ∼ 10 8\sim 108∼10 | 8000 80008000 | 无 |
| 11 ∼ 12 11\sim 1211∼12 | 2 × 10 5 2\times 10^52×105 | A |
| 13 ∼ 14 13\sim 1413∼14 | 2 × 10 5 2\times 10^52×105 | B |
| 15 ∼ 17 15\sim 1715∼17 | 2 × 10 5 2\times 10^52×105 | 无 |
| 18 ∼ 20 18\sim 2018∼20 | 2 × 10 6 2\times 10^62×106 | 无 |
特殊性质 A：字符串中的每个字符独立等概率地从字符集中选择。
特殊性质 B：字符串仅由a和b构成。
思路分析
本题要求统计字符串的所有非空连续子串中可消除的个数。一个字符串可消除，当且仅当可以通过反复删除相邻的相同字符，最终变为空串。
直接枚举所有子串并模拟消除过程的时间复杂度为 O(n²)，无法通过 n ≤ 2×10⁶ 的数据。需要线性或接近线性的算法。
关键转化：用栈模拟消除过程。维护一个栈，遍历字符串，若当前字符等于栈顶字符则弹出栈顶，否则压入当前字符。遍历完成后栈为空，则整个字符串可消除。
对于子串 s[l…r]，其可消除等价于：从 l 开始模拟消除过程，结束时栈为空。这等价于从 1 到 l-1 的栈状态与从 1 到 r 的栈状态相同。因为从 l 开始模拟相当于初始栈为空，处理完 s[l…r] 后栈为空，意味着从 l-1 的状态出发，处理 s[l…r] 后状态不变，所以 f[l-1] = f[r]，其中 f[i] 表示处理完前 i 个字符后的栈状态。
因此，问题转化为：求有多少对 (l, r) 满足 1 ≤ l ≤ r ≤ n 且 f[l-1] = f[r]。对于每个 r，统计有多少个 l 满足 f[l-1] = f[r]，累加即可。
实现细节：
- 用哈希值表示栈状态，便于比较和存储。
- 从左到右扫描，用栈维护当前状态，同时记录每个位置的哈希值。
- 使用哈希表记录每个哈希值出现的次数，扫描时累加以当前位置结尾的可消除子串数。
- 注意初始状态 f[0] 也要计入。
代码实现
#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongull;// 自然溢出哈希constintN=2000005;// 最大长度constintB=131;// 哈希基数intn;chars[N];// 字符串（1-indexed）charstk_c[N];// 栈中字符ull stk_h[N];// 栈中记录的前一个哈希值inttop;// 栈顶指针unordered_map<ull,int>cnt;// 哈希值出现次数intmain(){scanf("%d",&n);scanf("%s",s+1);// 从1开始读入ull h=0;// 当前哈希值cnt[0]=1;// 初始空栈状态出现一次（对应f[0]）top=0;ull ans=0;// 答案（可能很大，用ull）for(inti=1;i<=n;i++){charc=s[i];intv=c-'a'+1;// 字符映射为1~26if(top&&stk_c[top]==c){// 栈非空且栈顶字符相同，则弹出h=stk_h[top];// 恢复弹出前的哈希值top--;}else{// 否则压栈top++;stk_c[top]=c;stk_h[top]=h;// 记录压栈前的哈希值h=h*B+v;// 更新哈希值}ans+=cnt[h];// 以i结尾的可消除子串数等于之前相同状态的出现次数cnt[h]++;// 当前状态出现次数+1}printf("%llu\n",ans);return0;}功能分析
- 核心算法：利用栈模拟消除过程，将子串可消除的条件转化为前缀状态相等，从而通过哈希和计数在线性时间内求解。
- 时间复杂度：O(n)。每个字符最多入栈和出栈一次，哈希表操作均摊 O(1)。
- 空间复杂度：O(n)。栈和哈希表最多存储 n 个状态。
- 注意事项：
- 使用自然溢出哈希，基数 B 取 131，字符映射为 1~26 以避免前导零问题。
- 初始状态 f[0] 对应空栈，哈希值为 0，需预先加入计数。
- 答案可能达到 n(n+1)/2，需使用 64 位无符号整数。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
