luogu P9753题解

题意描述

有一个字符串, 请你求出有多少个字串可以经过若干次, 使它变成空串

其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。

## 思路1

可以枚举左端点, 再枚举右端点, 一边枚举一边判断是否合法

时间复杂度 $O(n^2)$

空间复杂度 $O(n)$

## 思路2

我们可以看出, 如果一个字串可以删除， 那么这一段可以完全抵消, 令这个字串的左端点为 $l$, 右端点为 $r$, 所以从 $1$ ~ $l - 1$ 和从 $1$ ~ $r$的栈是相同的(因为从 $l$ ~ $r$ 这一段的都被抵消了)可以用前缀和维护从 $1$ ~ $i$的栈出现数量, 再哈希统计答案

时间复杂度 $O(n \log n)$

空间复杂度 $O(n \log n)$

代码

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5;

unordered_map<unsigned long long, int>t;

unsigned long long wei[N];

string o;

int n;
unsigned long long ok;
char c;
long long ans;
int tot;

int main(){
cin >> n;
wei[0] = 1;
for(int i = 1; i <= 1000000; i++){
wei[i] = wei[i - 1] * 13331;
}
ok = 0;
t[0] = 1;
for(int i = 1; i <= n; ++i){
cin >> c;
if(o.size() && o[o.size() - 1] == c){
ok -= (o[o.size() - 1] - 'a' + 1) * wei[int(o.size())];
o.pop_back();
}
else{
o += c;
ok += (c - 'a' + 1) * wei[int(o.size())];
}
t[ok]++;
ans += t[ok] - 1;
}
cout << ans;
return 0;
}