题解：AT_abc433_c [ABC433C] 1122 Substring 2

Fake_Cry · 2025-11-28 19:29:49 · 题解

AT_abc433_c [ABC433C] 1122 Substring 2 题解

题目分析

需要在输入的字符串中找出所有满足条件的子串，条件如下：

• 长度为偶数。
• 前半部分都是同一个数字。
• 后半部分都是同一个数字。
• 最后一个数字比第一个数字大 1。

  解题思路

  考虑采用滑动窗口和双指针的方法高效解决。

使用循环枚举每个子串的起始位置。首先统计当前数字连续出现的长度，然后验证最后一个数字是否比第一个数字大 1（先判断简单的条件，可以降低一点复杂度）。如果是，则继续统计后半段连续相同数字的长度，此时有效子串数等于两个中的较小值，以确保前后两部分长度相等。注意可以直接跳到当前连续段结束的位置来避免重复计算。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
    string s;
    cin>>s;
    int n=s.size();//先求长度记录下来，减少下面的代码量
    int ans=0;
    for(int i=0;i<n;i++){//枚举起始位置
        int cnt=1;
        for(int j=i+1;j<n;j++){
            if(s[j]==s[i]) cnt++;
            else break;//小剪枝
        }
        if(i+cnt<n&&s[i+cnt]==s[i]+1){//先判断是否还剩下一段完整的子串，以及大 1 的条件
            int cnt2=1;
            for(int j=i+cnt+1;j<n;j++){
                if(s[j]==s[i+cnt]) cnt2++;
                else break;
            }
            ans+=min(cnt,cnt2);
        }
        i=i+cnt-1;//往后跳
    }
    cout<<ans;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);cout.tie(0);
    int _=1;//cin>>_;
    while(_--)solve();
    return 0;
}