专栏文章

题解：AT_abc433_c [ABC433C] 1122 Substring 2

NNottingham_Forest
AT_abc433_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min1hokn
此快照首次捕获于
2025/12/01 19:01
3 个月前
此快照最后确认于
2025/12/01 19:01
3 个月前
查看原文
题目传送门

思路

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

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...