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

一、题目解读

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

二、解题思路

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

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

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

三、解题步骤

    1. 初始化：定义哈希表stateCount，初始状态mask=0（空串）计数为1。

    2. 遍历处理：

        对每个字符，通过mask ^= (1 << (s[i] - 'a'))更新状态（异或操作实现字符添加/删除）。

        查询stateCount[mask]获取当前状态的出现次数，累加到答案。

        更新哈希表stateCount[mask]++。

    3. 结果输出：返回累计的等价子串总数。

四、代码与注释

#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[0] = 1;           // 空串状态初始化为1
   int mask = 0;                // 当前子串状态（二进制位表示）

   for (int i = 0; i < n; ++i) {
       mask ^= (1 << (s[i] - 'a'));  // 异或更新状态（字符转位操作）
       count += stateCount[mask];    // 累加已有状态的子串数
       stateCount[mask]++;          // 更新状态计数
   }

   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;
}

五、总结

    该算法巧妙利用位运算压缩子串状态，结合哈希表实现O(n)时间复杂度。核心在于将字符频率等价性问题转化为二进制位异或的数学性质，大幅降低计算成本。优化点包括状态初始化、异或操作的简洁性，以及哈希表的无序访问效率。对字符串处理与状态压缩类问题具有参考价值