题解：AT_agc036_b [AGC036B] Do Not Duplicate

看到删除操作就可以往这么一个方向上去想了：

设 $nxt_i$ 代表如果从 $i$ 开始插入，之后环形插入，第一次出现删空之后再往 $s$ 里面加数，加入的第一个数的位置。

（这里的位置可能会 $>n$ ，因为我们在记录位置的同时要记录是第几次走到这里，这样才能应对 $k$ 轮的变化）

之后直接暴力跳下一个位置。通过打表可以发现通过跳跃位置作为边建出的图是若干个环，因为每一个点都有正好一个入度、一个出度。

通过周期缩环的方式将

k

次循环操作改为

\le n+1

次操作。因为周期长度必然

\le n+1

。紧接着在环上的每一个点暴力跳跃，直到即将超过

n\times k

步。此时还剩下

\le n

步，裸暴力跳跃即可。

时间复杂度为

O(n)

，但未完全理解就会觉得它很抽象。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
}
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48); 
} 
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');
}
//找从 1 开始的循环节 
const int N=1e6+15;
int n,m,k;
int a[N]; 
int nxt[N];
int nxt_sum[N];	//按数值划分的 nxt  

int lst[N];
int stk[N];
int stk_idx;
#undef int
int main(){
	#define int long long
	n=read(),k=read(),m=n*k;
	for(int i=1;i<=n;i++){
		a[i]=a[i+n]=a[i+2*n]=read();
	}
	//在 long long 范围内 大多数内容都是能够去完成的！ 
	for(int i=3*n;i>=1;i--){
		nxt[i]=nxt_sum[a[i]]+1;
		nxt_sum[a[i]]=i;	//代表未来它会出现的位置 
		//实际上要对环进行各种改造 
	}
//	for(int i=1;i<=n;i++){
//		cout<<nxt[i]<<' ';
//	} 
//	cout<<endl;
	int now=1;
	int circle=0;	//代表一个经过点的环长  
	int circle_=0;	//环长 但是要除以数组长度  
	do{
		circle+=nxt[now]-now;
//		cout<<'$'<<circle<<endl;
		now=nxt[now];
		while(now>n)	now-=n;
//		cout<<'$'<<circle<<' '<<now<<endl; 
	}while(now!=1);
//	return 0;
//	cout<<circle<<endl;
	circle_=circle/n;
//	cout<<'&'<<circle<<' '<<circle_<<endl;
	k%=circle_;	//大幅减小环的数目！
//	cout<<'*'<<k<<endl;
	m=n*k;	//距离终点还有最后 m 步！！！！！
	int m1=m;
	now=1;//！！！！！ 
	while(1){
		if(m<nxt[now]-now)	break;	//在这里把它弹出！
		m-=nxt[now]-now;
		now=nxt[now];	//继续跳上去！  
		while(now>n)	now-=n;
//		if(now==1)	break; 
	} 
//	m=m1-m;
//	m1%=m; 
//	return 0;
//	cout<<m<<endl; 
	for(int i=m;i>=1;i--){
		int now=n-i+1;
		now=a[now];
		int lst_=lst[now];
//		cout<<'#'<<now<<' '<<lst_<<endl; 
		if(lst_!=0&&lst_<=stk_idx){
//			cout<<"谭总的世界-017"<<endl; 
			for(int j=lst_;j<=stk_idx;j++){
				lst[stk[j]]=0;
			}
			stk_idx=lst_-1;
		}
		else{
			stk_idx++;
			stk[stk_idx]=now;
			lst[now]=stk_idx;
		}
		
//		cout<<'^'<<stk_idx<<endl;
//		cout<<endl;
	}
	for(int i=1;i<=stk_idx;i++){
		write1(stk[i]);
	}
	putchar('\n');
	return 0;
} //一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！

题解：AT_agc036_b [AGC036B] Do Not Duplicate

文章操作

相关推荐

评论

题解：AT_agc036_b [AGC036B] Do Not Duplicate