G7012 [GESP202503 七级] 等价消除 题解

知识点：前缀异或、状态压缩、哈希计数。

解题思路

用26位掩码维护每个字母在前缀中出现次数的奇偶性，同一掩码的两个前缀夹出的子串可完全消除，用哈希计数。

为什么正确

每次删去两个相同字符不改变奇偶性；所有字母次数均为偶数时可分别配对删光，等价于前缀掩码相同。

易错点

本题不要求删去的两个字符相邻，不能套用相邻消除栈；非空子串由当前前缀与此前前缀配对。

复杂度

平均时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin>>n>>s;
    unordered_map<int,long long>cnt;
    cnt[0]=1;
    int mask=0;
    long long ans=0;
    for(char c:s) {
        mask^=1<<(c-'a');
        ans+=cnt[mask]++;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。