赛时
想到了一个规律，当一个字符串的头和首相等，并且中间的字符串同样可以被消除的话，那么这个大字串也就可以被消除。
虽然竭尽全力想到了这一点，不过还不知道如何实现，开始的想法是：
先使用 \(vector\) 来记录每一个字母所在的分别的下标，然后先从两个相邻字母的开始找（因为这样必定是可以消掉的），然后通过这个字串开始往两边遍历，一直找到找不下去为止。
然而，这样的想法是大错特错的，因为有 \(CBBAAC\) 这样的情况，按照我的思想是无法找到的，在考试中想到了 区间dp，同样的在考试中也想到了 栈 来找到一段回文字符串的方法，只是没有想到使用 栈 可以得到 \(50pts\) 的好成绩，思路还是很简单的：
每次枚举一个端点 \(l\) ，然后对这个 \([l, n]\) 的字串进行括号匹配，这时候就可以累加可以匹配的字符串，就可以完成。
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define rint register int
#define For(i, j, k) for(rint i = j; i <= k; i++)
using namespace std;
inline int read(){
int f = 1,x = 0;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-')f = -1;
ch = getchar();
}
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void print(int x){
if(x > 9)print(x / 10);
putchar(x % 10 + '0');
}
string a;
ll ans = 0;
const int ull base = 1e7 + 7;
ull H[2000010];
signed main(){
int n = read(); cin >> a;
a = ' ' + a; H[0] = 1;
For(i, 1, n){
H[i] = H[i - 1] * base;
}
For(i, 1, n){
stack<char> s;
ull cnt = 0;
For(j, i, n){
if(!s.empty() && s.top() == a[j])
cnt -= s.top() * H[s.size()], s.pop();
else s.push(a[j]), cnt += s.top() * H[s.size()];
if(cnt == 0)
ans++;
}
}
cout << ans;
return 0;
}
- Solve 1
果然正解其实就藏在骗分之中。
Hash + 栈
使用 Hash 处理现在枚举过的无法匹配的未匹配的字串的值，如 \(ABBA\) 假设我们处理到了 \(i = 3\) 那么剩下没有匹配的就会是 \(A\) ，这样我们就可以开始找到另一个 \(Hash\) 值表示 \(A\) 的字符串，因为 \(Hash\) 值是单调递增的（不考虑取模），所以如果之前有一个 \(Hash\) 值与现在的相等，那么说明，中间的这一段字符串一定就可以被消除。
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define rint register int
#define For(i, j, k) for(rint i = j; i <= k; i++)
using namespace std;
inline int read(){
int f = 1,x = 0;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-')f = -1;
ch = getchar();
}
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void print(int x){
if(x > 9)print(x / 10);
putchar(x % 10 + '0');
}
string a;
stack<char> s;
ull cnt = 0;
const ull base = 1e9 + 7;
ull H[2000010];
ll ans = 0;
unordered_map<ull, ll> sum;
signed main(){
int n = read(); cin >> a;
a = ' ' + a;
H[0] = 1;
For(i, 1, n){
H[i] = H[i - 1] * base;
}
sum[0] = 1;
For(i, 1, n){
if(!s.empty() && s.top() == a[i])
cnt -= s.top() * H[s.size()], s.pop();
else
s.push(a[i]), cnt += a[i] * H[s.size()];
ans += sum[cnt];
sum[cnt]++;
}
cout << ans;
return 0;
}
- Solve 2
这就与赛时想法比较像了。
运用结论，设 \(dp_i\) 表示以 \(i\) 为结尾的匹配字符串的个数。
那么肯定有以下的结论，令 \(last_i\) 表示与 \(a_i = a_{last_i}\) 的且 \([last_i, i]\) 可以被消除的最近的下标， \(dp_i\) 的改变一定是 \(dp_{last_i - 1} + 1\) ，如何去找到这个 \(last_i\) 呢？通过之前的思想，我们可以把大事化小，通过跳来解决 \(last_i \Leftarrow last_{last_i - 1} \dots\) 原理是什么呢，其实就是一直找回文字符串。
代码如下
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define rint register int
#define For(i, j, k) for(rint i = j; i <= k; i++)
#define down(i, j, k) for(rint i = k; i <= j; --i)
using namespace std;
inline int read(){
int f = 1,x = 0;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-')f = -1;
ch = getchar();
}
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void print(int x){
if(x > 9)print(x / 10);
putchar(x % 10 + '0');
}
ll to[2000010], dp[2000010], ans;
signed main(){
int n = read();
string a;
cin >> a;
a = ' ' + a;
For(i, 1, n){
for(int j = i - 1; j > 0; j = to[j] - 1){
if(a[j] == a[i]){
to[i] = j;break;
}
}
if(to[i])dp[i] = dp[to[i] - 1] + 1, ans += dp[i];
}
cout << ans;
return 0;
}