专栏文章

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

MMeickol
P12143题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mip3oj9l
此快照首次捕获于
2025/12/03 05:38
3 个月前
此快照最后确认于
2025/12/03 05:38
3 个月前
查看原文

后缀处理 + 字符串模拟

简单题，维护 nene 数组，用 neine_i 记录 ii 位置作为左端点最右能扩展到的位置。
显然 [i,nei][i,ne_i] 这段区间的子串是一个连续非递减子串，当该区间长度等于 11 时，符合题意好串的定义；当该区间长度大于 11 时，显然我们有办法将这个区间拆分成两部分，使得两部分都是连续非递减子串，于是也符合题意好串的定义。
同时，若记 p=neip=ne_i，显然区间为 [i,p][i,p] 的这个连续非递减子串可以和区间为 [p+1,nep+1][p+1,ne_{p+1}] 的这个连续非递减子串拼接，也符合题意好串的定义。
于是得出结论，对于位置 ii 而言，当其作为好串左端点，那么右端点可以选取为 [i,nep+1][i,ne_p+1]。考虑计算贡献即可。
一些细节可见下方代码。
CPP
#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;
}

评论

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

正在加载评论...