简答题 偏难
#20430

等价消除 时间限制:1 s,内存限制:512 MB 【问题描述】 小 A 有一个仅包含小写英文字母的字符串 。 对于一个字符串,如果能通过每次删去其中两个相同字…

等价消除

时间限制:1 s,内存限制:512 MB

【问题描述】

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

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

小 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|<=200000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;map&gt; using namespace std; const int N = 2e5 + 5; int n; char s[N]; map &lt;int, int&gt; m; long long ans; int main() {     scanf("%d", &amp;n);     scanf("%s", s + 1);     int v = 0;     m[v]++;     for (int i = 1; i &lt;= n; i++) {         v ^= 1 &lt;&lt; (s[i] - 'a');         ans += m[v];         m[v]++;     }     printf("%lld\n", ans);     return 0; }</pre>
这道题暂未补解析。