AT_abc433_c [ABC433C] 1122 Substring 2 题解

题目分析

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

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

解题思路

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

使用循环枚举每个子串的起始位置。首先统计当前数字连续出现的长度，然后验证最后一个数字是否比第一个数字大

1

（先判断简单的条件，可以降低一点复杂度）。如果是，则继续统计后半段连续相同数字的长度，此时有效子串数等于两个中的较小值，以确保前后两部分长度相等。注意可以直接跳到当前连续段结束的位置来避免重复计算。

代码

CPP

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

题解：AT_abc433_c [ABC433C] 1122 Substring 2

文章操作

AT_abc433_c [ABC433C] 1122 Substring 2 题解

题目分析

解题思路

代码

相关推荐

评论

题解：AT_abc433_c [ABC433C] 1122 Substring 2