专栏文章

题解：CF2010C2 Message Transmission Error (hard version)

ccyntmeay
CF2010C2题解参与者 1已保存评论 0

文章操作

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

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

题目大意

给你一个字符串 ss。求是否有字符串 tt 既是 ss 的前缀又是 ss 的后缀，并且 tt 的长度大于 ss 的一半。

题目做法

我们如果暴力枚举发现时间复杂度是 O(n2)O(n^2) 这样的复杂度明显不能接受。

做法

先求出字符串 ss 的最长公共前后缀的长度，我们将它叫做 hh，如果 t×2t \times 2 比 ss 的长度大，就是满足了长度大于 ss 的一半这个条件，那么原来的字符串就是答案。

为什么

当条件满足的时候，那么 ss 的最长公共前后缀就有相交的部分，相交的地方就是原串发生合并的地方，所以可以知道原串就是 ss 的最长公共前后缀。

给出代码

CPP
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,d;
int ans;
int a[N];
int main(){
	scanf("%d%d",&n,&d);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
	}
	for(int i=1; i<=n; i++){
		int l=lower_bound(a+1,a+n+1,a[i]-d)-a;
		int r=upper_bound(a+1,a+n+1,a[i]+d)-a-1;
		ans+=(3*i-2*l-r+1)*(r-i)/2;
	}
	printf ("%d\n",ans);
	return 0;
}

评论

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

正在加载评论...