A28336. 等价消除
填空题
困难
知识点
题目描述
等价消除
题目描述
小 A 有一个仅包含小写英文字母的字符串S 。
对于一个字符串，如果能通过每次删去其中两个相同字符的方式，将这个字符串变为空串，那么称这个字符串是可以被等价消除的。
小 A 想知道 S有多少子串是可以被等价消除的。
一个字符串 S'是 S的子串，当且仅当删去 S的某个可以为空的前缀和某个可以为空的后缀之后，可以得到 S'。
输入格式
第一行，一个正整数|S| ，表示字符串S 的长度。
第二行，一个仅包含小写英文字母的字符串S 。
输出格式
一行，一个整数，表示答案。
样例
输入样例 1
7
aaaaabb输出样例 1
9输入样例 2
9
babacabab输出样例 2
2数据范围
对于20%的测试点，保证S中仅包含 a 和 b 两种字符。
对于另外20%的测试点，保证1≤|S|≤2000 。
对于所有测试点，保证1≤|S|≤2×105 。
参考答案
#include <cstdio>
#include <map>
using namespace std;
const int N = 2e5 + 5;
int n;
char s[N];
map <int, int> m;
long long ans;
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
int v = 0;
m[v]++;
for (int i = 1; i <= n; i++) {
v ^= 1 << (s[i] - 'a');
ans += m[v];
m[v]++;
}
printf("%lld\n", ans);
return 0;
}
上一题
下一题