这个能卡吗
查看原帖
这个能卡吗
221729
qsceszthn楼主2021/10/24 12:34

把双指针扫到的全都check一遍,把考场代码数组开小和边界补上就过了

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define ms(a,vl) memset(a,vl,sizeof(a))
using namespace std;
const int N=5e5+5;
int n,a[N],cnt[N];
vector<int>ans;
int ck(int l,int r){
	int x=-1,y=-1,ff=0;
	F(i,l,r)if(a[i]==a[1]){
		x=y=i;
		break;
	}
	vector<int>res,d;
	if(~x){
		res.push_back(0);
		int bg=2,ed=2*n,f=1;
		while(y-x+1<n){
			if(l<=x-1&&bg<l&&a[x-1]==a[bg])res.push_back(0),d.push_back(0),--x,++bg;
			else if(y+1<=r&&bg<l&&a[y+1]==a[bg])res.push_back(0),d.push_back(1),++y,++bg;
			else if(l<=x-1&&r<ed&&a[x-1]==a[ed])res.push_back(1),d.push_back(0),--x,--ed;
			else if(y+1<=r&&r<ed&&a[y+1]==a[ed])res.push_back(1),d.push_back(1),++y,--ed;
			else{f=0;break;}
		}
		
		if(f){
			dF(i,(int)d.size()-1,0)res.push_back(d[i]);
			ans=ans.size()?min(ans,res):res;
		}
		ff|=f;
	}
	res.clear(),d.clear();
	x=-1,y=-1;
	F(i,l,r)if(a[i]==a[2*n]){
		x=y=i;
		break;
	}
	if(~x){
		res.push_back(1);
		int bg=1,ed=2*n-1,f=1;
		while(y-x+1<n){
			if(l<=x-1&&bg<l&&a[x-1]==a[bg])res.push_back(0),d.push_back(0),--x,++bg;
			else if(y+1<=r&&bg<l&&a[y+1]==a[bg])res.push_back(0),d.push_back(1),++y,++bg;
			else if(l<=x-1&&r<ed&&a[x-1]==a[ed])res.push_back(1),d.push_back(0),--x,--ed;
			else if(y+1<=r&&r<ed&&a[y+1]==a[ed])res.push_back(1),d.push_back(1),++y,--ed;
			else{f=0;break;}
		}
		if(f){
			dF(i,(int)d.size()-1,0)res.push_back(d[i]);
			ans=ans.size()?min(ans,res):res;
		}
		ff|=f;
	}
	return ff;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		F(i,1,2*n)scanf("%d",&a[i]);
		int l=1,al=-1,ar=-1;
		ans.clear();
		F(r,1,2*n){
			++cnt[a[r]];
			if(cnt[a[r]]>1){
				while(l<=r&&cnt[a[r]]>1){
					--cnt[a[l++]];
				}
			}
			if(r-l+1==n){
				if(ck(l,r)){
					al=l,ar=r;
				}
			}
		}
		if(~al){
			F(i,0,(int)ans.size()-1)putchar(ans[i]?'R':'L');
			puts("L");
		}else{
			puts("-1");
		}
		F(i,1,n)cnt[i]=0;
	}
}
/*
2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
*/
2021/10/24 12:34
加载中...