专栏文章

题解：AT_abc381_d [ABC381D] 1122 Substring

ddaitangchen2008
AT_abc381_d题解参与者 1已保存评论 0

文章操作

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

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

分析：

分成两种情况：从 1 开始和从 2 开始，分类讨论。
记以每个 ii 位置为最后位置的串的开头为 jj，那答案即为最大的 i−ji-j。
每次更新 jj 时，先判断相邻的两个位置是否相同。如果不同就更新；再判断是否出现过，出现过再更新 jj。每次操作结束后更新位置。
时间复杂度 O(n)O(n)，可以通过。

代码：

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fi first
#define se second
#define ce continue
const int N=5e5+10;
const int mod=998244353;
priority_queue<int> q;
set<int> s;
stack<int> sta;
int n;
int a[N];
string st;
int mhash[N];
signed main()
{
	int n;
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int last=0;
	int duan=0;
	for(int i=2;i<=n;i+=2)
	{
		if(a[i]!=a[i-1])
		{
			duan=i;
			continue;
		}
		ans=max(ans,i-max(duan,mhash[a[i]]));
		if(mhash[a[i]]!=0)
		duan=max(duan,mhash[a[i]]);
		mhash[a[i]]=i;
	}
	for(int i=1;i<=N-300;i++)
		mhash[i]=0;
	duan=1;
	for(int i=3;i<=n;i+=2)
	{
		if(a[i]!=a[i-1])
		{
			duan=i;
			continue;
		}
		ans=max(ans,i-max(duan,mhash[a[i]]));
		if(mhash[a[i]]!=0)
		duan=max(duan,mhash[a[i]]);
		mhash[a[i]]=i;
	}
	cout<<ans<<endl;
	return 0;
 }

评论

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

正在加载评论...