AC代码(非本人)
查看原帖
AC代码(非本人)
131890
Eroi楼主2021/10/25 16:02
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N=1e6+10;
inline int read(){
	int f=1, x=0; char ch=getchar();
	while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
	return f*x;
}
int T, a[N], num[N], to[N], n;
int vis[N];
int stk[N], l, r;
bool dfs(int k){
	if(k==n+1) return 1;
	bool flag=0;
	if((vis[to[l]+1]||vis[to[l]-1]||k==1)&&!vis[l]){
		vis[to[l]]=k; ++l; stk[k]=1;
		flag|=dfs(k+1); --l; vis[to[l]]=0;
	}
	if(flag) return 1;
	if((vis[to[r]+1]||vis[to[r]-1]||k==1)&&!vis[r]){
		vis[to[r]]=k; --r; stk[k]=2;
		flag|=dfs(k+1); ++r; vis[to[r]]=0;
	}
	return flag;
}
signed main(void){

	T=read();
	while(T--){
		n=read(); l=1, r=n<<1;
		memset(vis, 0, sizeof vis);
		memset(num, 0, sizeof num);
		memset(stk, 0, sizeof stk);
		memset(to, 0, sizeof to);
		for(int i=1; i<=n<<1; ++i) a[i]=read();
		for(int i=1; i<=n<<1; ++i){
			if(!num[a[i]]) num[a[i]]=i;
			else to[i]=num[a[i]], to[num[a[i]]]=i;
		}
		bool flag=dfs(1);
		if(!flag) { puts("-1"); continue; }
		l=1, r=n<<1;
		for(int i=1; i<=n; ++i){
			stk[i]==1 ? printf("L") : printf("R");
			if(stk[i]==1) vis[to[l++]]=i;
			else vis[to[r--]]=i;
		}
		while(l<=r){
			if(vis[l]>=vis[r]) printf("L"), ++l;
			else printf("R"), --r;
		}
		puts("");
	}
	return 0;
}
2021/10/25 16:02
加载中...