洛谷 P11965 [GESP202503 七级] 等价消除-普及/提高-

题目描述

小 A 有一个仅包含小写英文字母的字符串 $S$。

对于一个字符串，如果能通过每次删去其中两个相同字符的方式，将这个字符串变为空串，那么称这个字符串是可以被等价消除的。

小 A 想知道 $S$ 有多少子串是可以被等价消除的。

一个字符串 $S^{\prime }$ 是 $S$ 的子串，当且仅当删去 $S$ 的某个可以为空的前缀和某个可以为空的后缀之后，可以得到 $S^{\prime }$。

输入格式

第一行，一个正整数 $|S|$，表示字符串 $S$ 的长度。

第二行，一个仅包含小写英文字母的字符串 $S$。

输出格式

一行，一个整数，表示答案。

输入输出样例 #1

输入 #1

7
aaaaabb

输出 #1

9

输入输出样例 #2

输入 #2

9
babacabab

输出 #2

2

说明/提示

本题采用捆绑测试。

对于 $20\%$ 的测试点，保证 $S$ 中仅包含 $a$ 和 $b$ 两种字符。

对于另外 $20\%$ 的测试点，保证 $1\le |S|\le 2000$。

对于所有测试点，保证 $1\le |S|\le 2\times 10^5$。

solution

统计每个字母出现的次数的前缀和，其实只需要记录奇偶即可，为了高效记录可以，可以用一个二进制整数表示每个字母出现的次数是奇数次还是偶数次，如果前面某个时刻和本刻相同，则说明中间这部分可以消除

代码

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "unordered_map"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"using namespace std;int n, x;
long long sum;unordered_map<int, int> m;int main() {char c;cin >> n;m[0] = 1;for (int i = 0; i < n; i++) {cin >> c;x ^= 1 << (c - 'a');sum += m[x];m[x]++;}cout << sum;
}

结果