做题笔记（二）

SnapYust繁华的小窝 / 2024-08-09 / 原文

[CSP-S 2023] 消消乐

题目传送门

[CSP-S 2023] 消消乐

思路

考虑 DP。

显然，设 $f_i$ 表示以位置 $i$ 结尾的可消除序列的个数，我们对每一个可消除序列考虑模型，大概就是这个样子：$\text{a}\cdots\text{ab}\cdots\text{b}$。

那么我们当前位置为 $i$，前一个可以与 $i$ 匹配的最大的下标为 $low_i$，显然：

\[f_i=f_{low_i-1}+1 \]

到这里其实都很简单的，去年的我考场上也是想到这里就戛然而止，最后写了一个 50pts 的暴力遗憾离场。

但我们可以考虑一个一个往前找，就是那个 $O(n^2)$ 的暴力做法，考虑优化。

假设当前位置为 $i$，$low_{1\rightarrow i}$ 已经求出，那么我们注意到类似于 $\text{a}\cdots\text{a}$ 的子串中的省略号一定是由若干个可消除字串。那么我们可以一个一个往前跳。

由于最多只有 $26$ 个字母，所以每一次向前跳的期望应该是一个常数级别，所以时间复杂度是线性的。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

string s;
int f[2000005]={0},n,ans=0;
int last[2000005]={0};

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>s; s=" "+s;
	
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>0;j=last[j]-1){
			if(s[i]==s[j]){
				last[i]=j;
				break;
			}
		}
		
		if(last[i]!=0)
			f[i]+=(1ll+f[last[i]-1]);
	}
	
	for(int i=1;i<=n;i++)
		ans+=f[i];
		
	cout<<ans<<endl;
	
	return 0;
}