题解：P12143 [蓝桥杯 2025 省 A] 好串的数目

Meickol · 2025-06-12 16:34:45 · 题解

后缀处理 + 字符串模拟

简单题，维护 ne 数组，用 ne_i 记录 i 位置作为左端点最右能扩展到的位置。

显然 [i,ne_i] 这段区间的子串是一个连续非递减子串，当该区间长度等于 1 时，符合题意好串的定义；当该区间长度大于 1 时，显然我们有办法将这个区间拆分成两部分，使得两部分都是连续非递减子串，于是也符合题意好串的定义。

同时，若记 p=ne_i，显然区间为 [i,p] 的这个连续非递减子串可以和区间为 [p+1,ne_{p+1}] 的这个连续非递减子串拼接，也符合题意好串的定义。

于是得出结论，对于位置 i 而言，当其作为好串左端点，那么右端点可以选取为 [i,ne_p+1]。考虑计算贡献即可。

一些细节可见下方代码。

#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
const int N=1e5+5;
int stk[N],top;
int ne[N];
void solve(){
    string s;
    cin>>s;
    int n=s.size();
    s=" "+s;
    ne[n]=n;
    per(i,n-1,1){
        if(s[i]==s[i+1] || s[i]+1==s[i+1]) ne[i]=ne[i+1];
        else ne[i]=i;
    }
    LL ans=0;
    rep(i,1,n){
        int p=ne[i];
        if(p!=n) p=ne[p+1];
        int cnt=p-i+1;
        if(cnt>=0) ans+=cnt;
    }
    cout<<ans;
}