简答题
偏难
#20430
等价消除 时间限制:1 s,内存限制:512 MB 【问题描述】 小 A 有一个仅包含小写英文字母的字符串 。 对于一个字符串,如果能通过每次删去其中两个相同字…
等价消除
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有一个仅包含小写英文字母的字符串 。
对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字符串是可以被等价消除的。
小 A 想知道 S 有多少子串是可以被等价消除的。
一个字符串 S' 是 S 的子串,当且仅当删去 S 的某个可以为空的前缀和某个可以为空的后缀之后,可以得到 S'。
【输入描述】
第一行,一个正整数 |S|,表示字符串 S 的长度。
第二行,一个仅包含小写英文字母的字符串 S。
【输出描述】
一行,一个整数,表示答案。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 S 中仅包含 a 和 b 两种字符。
对于另外 20% 的测试点,保证 1<=|S|<=2000。
对于所有测试点,保证 1<=|S|<=200000。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。