专栏文章

题解：P13339 [EGOI 2025] Gift Boxes / 礼品盒

xxixisuper九倍体水稻
P13339题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minach7l
此快照首次捕获于
2025/12/01 23:09
3 个月前
此快照最后确认于
2025/12/01 23:09
3 个月前
查看原文
显然是可以双指针的。
考虑左侧取得一个极长的串满足 [0,l][0,l] 中没有重复的数，在该情况下从右侧取得一个与 [0,l][0,l] 中没有重复的数且 [r,n−1][r,n-1] 中也没有重复的数。
令 ll 逐渐减小，并逐渐更新 rr，记录下当前情况下的最优 [l,r][l,r] 即可，时间复杂度线性。
CPP
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll int 
using namespace std;
const ll N=5e5+10;
ll T,n,a[N],tong[N],cnt;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T>>n;
	for(ll i=1;i<=n;i++) cin>>a[i];
	ll l=0,r=n+1;
	while(tong[a[r-1]]==0){
		r--;cnt++;tong[a[r]]++; 
	}
	while(tong[a[l+1]]==0){
		l++;cnt++;tong[a[l]]++; 
	}
	ll ansL=0,ansR=n+1,anscnt=0;
	for(;r<=n+1;r++){
		while(tong[a[l+1]]==0){
			l++;cnt++;tong[a[l]]++; 
		}
		if(cnt>=anscnt){
			if(cnt==anscnt){
				if(r-l<ansR-ansL) ansR=r,ansL=l;
			}
			else{
				anscnt=cnt;
				ansR=r,ansL=l;
			}
		}
		tong[a[r]]--;
		cnt--;
	}
	cout<<ansL<<' '<<ansR-2;
	return 0;
}

评论

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

正在加载评论...