P12143 [蓝桥杯 2025 省 A] 好串的数目 - 洛谷

我们可以发现长度为 1 或 2 的字符串一定是好串，而长度为 3 以上的字符串要么本身为连续非递减子串，要么由 2 个连续非递减子串拼接而成。所以我们可以提前预处理出所有连续非递减子串，记录起点与终点，最后计算答案即可。对于本身是连续非递减子串的好串，它一定在某个连续非递减子串中，可以用等差数列求出；对于由 2 个连续非递减子串拼接而成的好串，可以用乘法原理，将连续两个区间长度相乘即可求出。

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 1e18
#define eps 1e-9
#define ls 2*k
#define rs 2*k+1
#define endl "\n"
#define il inline
using namespace std;
const int N=1e6+5,M=3e5;
const int mod=998244353;
inline int read(){
	int x(0),f(1);char c=getchar();
	while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
string s;
int n,ans,a[N];
signed main(){
	cin>>s;
	n=s.size();
	vector<pair<int,int> >pre;
	int st=1;
	for(int i=1;i<=n;i++){
		a[i]=s[i-1]-'0';
		if(i>1 && a[i]!=a[i-1] && a[i]!=a[i-1]+1){
			pre.push_back({st,i-1});
			st=i;
		}
	}
	pre.push_back({st,n});
	int abc=0;
	for(auto e : pre){
		int len=e.second-e.first+1;
		ans+=(len+1)*len/2;
		ans+=len*abc;
		abc=len;
	} 
	cout<<ans;
	return 0;
}