2025年GESP七级等价消除（洛谷P11965）代码解析与优化策略

19339201706

一、题目解读

    2025年GESP七级考试中的“等价消除（洛谷P11965）”问题要求统计给定字符串中满足等价条件的子串数量。所谓“等价子串”，是指子串中所有字符出现的次数均相同。题目需要高效算法解决，考验对字符串处理和状态压缩的掌握。

二、解题思路

采用位运算+哈希表的核心思想：

    1. 将字符映射为二进制位：每个字符（如'a'-'z'）对应一位（如1<<('a'-'a')到1<<('z'-'a')），子串状态为各字符位异或结果。

    2. 统计等价子串：若当前状态已存在，说明存在前缀与该子串等价，其子串数量计入答案；同时更新哈希表记录当前状态出现次数。

三、代码与注释

1. #include <iostream>
   
2. #include <string>
   
3. #include <unordered_map>
   
4. using namespace std;
   
5. 
   
6. // 核心函数：统计等价子串数量
   
7. long long countEquivalentSubstrings(const string& s) {
   
8.    int n = s.size();
   
9.    long long count = 0;          // 答案计数器
   
10.    unordered_map<int, int> stateCount; // 记录状态出现次数
    
11.    stateCount[0] = 1;           // 空串状态初始化为1
    
12.    int mask = 0;                // 当前子串状态（二进制位表示）
    
13. 
    
14.    for (int i = 0; i < n; ++i) {
    
15.        mask ^= (1 << (s[i] - 'a'));  // 异或更新状态（字符转位操作）
    
16.        count += stateCount[mask];    // 累加已有状态的子串数
    
17.        stateCount[mask]++;          // 更新状态计数
    
18.    }
    
19. 
    
20.    return count;
    
21. }
    
22. 
    
23. int main() {
    
24.    ios::sync_with_stdio(false);
    
25.    cin.tie(nullptr);
    
26.    
    
27.    int n;
    
28.    string s;
    
29.    cin >> n >> s;   // 输入（题目可能有多组数据，但此处简化）
    
30.    cout << countEquivalentSubstrings(s) << endl;
    
31.    return 0;
    
32. }

复制代码

原文：2025年GESP七级等价消除（洛谷P11965）代码解析与优化策略