专栏文章

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

IInnitTimmer_
P13339题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mina9wvt
此快照首次捕获于
2025/12/01 23:07
3 个月前
此快照最后确认于
2025/12/01 23:07
3 个月前
查看原文
题意可以理解为：我们选出一个区间 [l,r][l,r]，使得我们没有选到的数中没有重复的数字。
考虑维护两个没有被选择的段，下文设其为 [1,L][1,L] 和 [R,n][R,n]。
首先我们枚举每一个 LL，然后我们发现左边区间的每一个数都不能在右边出现过，所以我们可以预处理出来左边每一个数其在右边第一次出现的位置，设这个位置为 xx，那么则有 R>max⁡xR > \max x，所以我们想求这个最小的选择的区间长度就是区间 [L+1,R−1][L+1,R-1] 了。
上面的 max⁡x\max x 可以在枚举 LL 的时候直接求一个前缀最大值。
然而这并没有结束，可能右边自己出现了两个相同的，或者左边自己出现了两个相同的，判断一下即可。
注意左边一点也不选的情况，时间复杂度 O(n)O(n)。
CPP
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool Test_MLE_start;
constexpr int N=5*1e5+10;
int _=1,T,n,R=0,ansL,ansR,ans=2e9,ok=0,a[N],maxn[N],ton[N];
bool flg=0;
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("gift.in","r",stdin);
	freopen("gift.out","w",stdout);
}inline void clr(){
//	Don't forget!

}bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
	files(); 
//	_=reads();
	while(_--){
		clr();T=reads(),n=reads();
		for(int i=1;i<=n;i++) a[i]=reads();
		for(int i=n;i>=1;i--){
			if(!maxn[a[i]]) maxn[a[i]]=i+1;
			if(!ton[a[i]]) ton[a[i]]=1;
			else if(!flg&&ton[a[i]]) ok=i+1,flg=1;
		}memset(ton,0,sizeof(ton));
		if(ok<ans) ans=ok,ansL=1,ansR=ok-1;
		for(int i=0;i<T;i++) maxn[i]=max(maxn[i],ok);
		for(int i=1;i<=n;i++){
			if(!ton[a[i]]) ton[a[i]]=1;
			else{ok=i-1;break;}
		}
		for(int L=1;L<=ok;L++){
			R=max(R,maxn[a[L]]);
			int pl=L+1,pr=R-1;
			if(pl>pr) continue;
			if(pr-pl+1<ans){
				ans=pr-pl+1;
				ansR=pr,ansL=pl;
			}
		}printf("%d %d\n",ansL-1,ansR-1);
	}return 0;
}
/*
2 3
0 1 0
*/

评论

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

正在加载评论...