CSP-S 2023 消消乐 题解

考虑预处理。 处理 数组，每次走到一个位置 ，往前搜索。 当前位置不等于 则通过这个位置继续往前查找。一直到当前位置等于 ，或者到达最前端则停止。 接下来进行第二次处理。 由于已经对 进行过预处理，在计算时只需要从有值的点分别往前统计即可。 最后求一遍和。

感谢学弟 @kibi 的优化！

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2000010;
int n, a[N], f[N],tot;
char s[N];
signed main() {
	memset(a, -1, sizeof a);
    cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=n;i++) a[i]=i-1;
    for(int i=1;i<=n;i++){
        while(s[a[i]]!=s[i])
        {
        	a[i]=a[a[i]]-1;
            if(a[i]<=-1) break;
		}
    }
  //  for(int i=1;i<=n;i++) cout<<a[i]<<' ';
  //  cout<<endl;
    for(int i=1;i<=n;i++) {
        if(a[i]>0) f[i]=f[a[i]-1]+1;
    }
    for(int i=1;i<=n;i++) {
        tot+=f[i];
    }
    cout<<tot<<endl;
}