2025年GESP七级等价消除（洛谷P11965）代码解析与优化策略
https://www.xinaozhilu.cn/zb_users/upload/2025/06/202506061749192723359737.jpg
一、题目解读 2025年GESP七级考试中的“等价消除（洛谷P11965）”问题要求统计给定字符串中满足等价条件的子串数量。所谓“等价子串”，是指子串中所有字符出现的次数均相同。题目需要高效算法解决，考验对字符串处理和状态压缩的掌握。二、解题思路采用位运算+哈希表的核心思想： 1. 将字符映射为二进制位：每个字符（如'a'-'z'）对应一位（如1<<('a'-'a')到1<<('z'-'a')），子串状态为各字符位异或结果。 2. 统计等价子串：若当前状态已存在，说明存在前缀与该子串等价，其子串数量计入答案；同时更新哈希表记录当前状态出现次数。三、代码与注释
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// 核心函数：统计等价子串数量
long long countEquivalentSubstrings(const string& s) {
int n = s.size();
long long count = 0; // 答案计数器
unordered_map<int, int> stateCount; // 记录状态出现次数
stateCount = 1; // 空串状态初始化为1
int mask = 0; // 当前子串状态（二进制位表示）
for (int i = 0; i < n; ++i) {
mask ^= (1 << (s - 'a'));// 异或更新状态（字符转位操作）
count += stateCount; // 累加已有状态的子串数
stateCount++; // 更新状态计数
}
return count;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n >> s; // 输入（题目可能有多组数据，但此处简化）
cout << countEquivalentSubstrings(s) << endl;
return 0;
}原文：2025年GESP七级等价消除（洛谷P11965）代码解析与优化策略
页:
[1]