题解：AT_abc433_c [ABC433C] 1122 Substring 2

Nottingham_Forest · 2025-11-24 17:42:40 · 题解

题目传送门

思路

暴力是不可取的，我们需要优化。

我们可以枚举满足条件的子串的结束位置，因为要想对答案有贡献，只能选上一个连续的段，所以我们可以用一个数组记录上一个连续的段的信息，再与现在的段比较即可。

代码

#include<bits/stdc++.h>
using namespace std;
string s;
struct node
{
    int t;
    char c;
}a[1000005];
int cnt,l,ans;
int main(){
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(i>0)
        {
            if(s[i]!=s[i-1]) 
            {
                a[++cnt].c=s[i-1];
                a[cnt].t=l;
                l=1;
            }
            else
            {
                l++;
            }
        }
        else
        {
            l++;
        }
        if(cnt>0)
        {
            if(char(a[cnt].c+1)==char(s[i])&&l<=a[cnt].t)  ans++; 
        }

    }
    cout<<ans;
}