: 等价消除)
2025年3月GESP真题及题解(C++七级): 等价消除
题目描述
小 A 有一个仅包含小写英文字母的字符串S SS。
对于一个字符串，如果能通过每次删去其中两个相同字符的方式，将这个字符串变为空串，那么称这个字符串是可以被等价消除的。
小 A 想知道S SS有多少子串是可以被等价消除的。
一个字符串S ′ S'S′是S SS的子串，当且仅当删去S SS的某个可以为空的前缀和某个可以为空的后缀之后，可以得到S ′ S'S′。
输入格式
第一行，一个正整数∣ S ∣ |S|∣S∣，表示字符串S SS的长度。
第二行，一个仅包含小写英文字母的字符串S SS。
输出格式
一行，一个整数，表示答案。
输入输出样例 1
输入 1
7 aaaaabb输出 1
9输入输出样例 2
输入 2
9 babacabab输出 2
2说明/提示
对于20 % 20\%20%的测试点，保证S SS中仅包含a aa和b bb两种字符。
对于另外20 % 20\%20%的测试点，保证1 ≤ ∣ S ∣ ≤ 2000 1 \leq |S| \leq 20001≤∣S∣≤2000。
对于所有测试点，保证1 ≤ ∣ S ∣ ≤ 2 × 10 5 1 \leq |S| \leq 2 \times 10^51≤∣S∣≤2×105。
题目分析
核心思路
题目要求找出字符串S SS中所有可以被"等价消除"的子串。根据定义，一个字符串能被等价消除，当且仅当其中每个字符的出现次数都是偶数。
因此，问题转化为：找出S SS中所有子串，使得每个字符的出现次数都是偶数。
关键观察
奇偶性状态压缩：因为只有小写字母（26种），可以用一个 26 位的二进制数表示每个字符出现次数的奇偶性（0表示偶数次，1表示奇数次）。
前缀异或思想：
- 定义
prefix[i]表示前 i 个字符的奇偶性状态 - 子串
[l, r]的状态 =prefix[r] ^ prefix[l-1] - 子串满足条件 ⇔
prefix[r] ^ prefix[l-1] = 0⇔prefix[r] = prefix[l-1]
- 定义
转化为计数问题：对于每个位置 r，统计有多少个 l (0 ≤ l < r) 使得
prefix[l] = prefix[r]。高效实现：使用哈希表记录每个状态出现的次数。
算法步骤
- 初始化状态为 0，表示空字符串的奇偶性（所有字符出现0次，都是偶数）
- 遍历字符串的每个字符：
- 更新当前奇偶性状态（异或对应字符的位）
- 当前状态的出现次数 = 该状态之前出现的次数
- 这些次数就是新增的满足条件的子串数量
- 更新该状态的计数
- 累加所有满足条件的子串数量
时间复杂度
- O(n)，其中 n 是字符串长度
- 使用哈希表实现状态计数的 O(1) 访问
空间复杂度
- O(min(n, 2²⁶))，最多存储 n+1 个不同的状态
代码实现
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;string s;cin>>n>>s;// 状态压缩：用int的低26位表示26个字母的奇偶性intstate=0;// 当前前缀的奇偶性状态// 哈希表：记录每个状态出现的次数unordered_map<int,longlong>cnt;cnt[0]=1;// 空前缀的状态出现1次longlongans=0;// 结果可能很大，用long long// 遍历字符串for(charc:s){// 更新状态：异或对应字符的位intbit=c-'a';state^=(1<<bit);// 当前状态之前出现的次数 = 新增的满足条件的子串数ans+=cnt[state];// 更新该状态的计数cnt[state]++;}cout<<ans<<endl;return0;}功能分析
核心功能
- 状态表示：使用整数的二进制位表示26个字母的奇偶性
- 前缀计算：通过异或运算高效更新状态
- 计数统计：使用哈希表记录状态出现次数
- 子串计数：通过状态匹配计算满足条件的子串数
正确性证明
- 必要性：如果子串能被等价消除，则每个字符出现偶数次，所以子串状态为0
- 充分性：如果子串状态为0，可以通过配对删除所有字符
- 计数正确：
prefix[r] = prefix[l]等价于子串[l+1, r]状态为0
示例分析
示例1：
输入：7 aaaaabb 处理过程： 位置0: state=0, cnt[0]=1, ans+=1 → ans=1, cnt[0]=2 位置1: state=1(a), cnt[1]=0, ans+=0 → ans=1, cnt[1]=1 位置2: state=0, cnt[0]=2, ans+=2 → ans=3, cnt[0]=3 位置3: state=1, cnt[1]=1, ans+=1 → ans=4, cnt[1]=2 位置4: state=0, cnt[0]=3, ans+=3 → ans=7, cnt[0]=4 位置5: state=3(a,b), cnt[3]=0, ans+=0 → ans=7, cnt[3]=1 位置6: state=1, cnt[1]=2, ans+=2 → ans=9, cnt[1]=3 输出：9示例2：
输入：9 babacabab 处理过程类似，最终输出2各种学习资料，助力大家一站式学习和提升！！！
#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;}
