28pts求救
查看原帖
28pts求救
353046
k014楼主2023/10/20 20:10
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
int n,t;
int k1,k2;
struct node{
	int val,id;
};
node a[2*N];
bool xl[2*N];
int fflg=0;
char str1[N],str2[N];
void js(int cs){
	fflg=0;
	int cnt=1;
	int k;
	node l1,r1,l2,r2;
	if(cs==0){
		str1[1]='L'; 
		l1=a[2];
		r1=a[n*2];
		k=k1;
		l2=a[k-1];
		r2=a[k+1];
	}
	else{
		str1[1]='R';
		l1=a[1];
		r1=a[n*2-1];
		k=k2;
		l2=a[k-1];
		r2=a[k+1];		
	}
	for(int i=2;i<=n;i++){//已选数量 
		if(l1.val==l2.val&&l1.id!=l2.id&&xl[l1.id]+xl[l2.id]==0){
			xl[l1.id]=1;
			xl[l2.id]=1;
			str1[i]='L';
			l1=a[l1.id+1];
			str2[n+1-i]='L';
			l2=a[l2.id-1];
			continue;

		}
		if(l1.val==r2.val&&l1.id!=r2.id&&xl[l1.id]+xl[r2.id]==0){
			xl[l1.id]=1;
			xl[r2.id]=1;
			str1[i]='L';
			l1=a[l1.id+1];
			str2[n+1-i]='R';
			r2=a[r2.id+1];
			continue;

		}
		if(r1.val==l2.val&&r1.id!=l2.id&&xl[r1.id]+xl[l2.id]==0){
			xl[r1.id]=1;
			xl[l2.id]=1;
			str1[i]='R';
			r1=a[r1.id-1];
			str2[n+1-i]='L';
			l2=a[l2.id-1];
			continue;

		}
		if(r1.val==r2.val&&r1.id!=r2.id&&xl[r1.id]+xl[r2.id]==0){
			xl[r1.id]=1;
			xl[r2.id]=1;
			str1[i]='R';
			r1=a[r1.id-1];
			str2[n+1-i]='R';
			r2=a[r2.id+1];
			continue;
			
		}
		if(i<=n){
			fflg=-1;
			break;
		}
	}
} 

int main(){
	scanf("%d",&t);
	while(t--){
		memset(xl,0,sizeof(xl));
		int fg=1;
		scanf("%d",&n);
		for(int i=1;i<=2*n;i++){
			scanf("%d",&a[i].val);
			a[i].id=i;
			if(a[i].val==a[1].val){
				k1=i;
			}
			if(a[i].val==a[n*2].val){
				k2=i;
			}
		}
		for(int i=1;i<=2*n;i++){
			if(a[i].val!=a[2*n+1-i].val){
				fg=0;
			}
		}
		if(fg==1){
			for(int i=1;i<=2*n;i++){
				cout<<"L";
			}
			cout<<endl;
			continue;
		}
		if(a[1].val==a[2*n].val){
			cout<<-1<<endl;
			continue;
		}
        str2[n]='L';		
		js(0);
		if(fflg==-1){
			memset(xl,0,sizeof(xl));
			js(1);
		}
		if(fflg==-1){
			cout<<fflg<<endl;
			continue;
		}
		for(int i=1;i<=n;i++){
			cout<<str1[i]; 
		}
		for(int i=1;i<=n;i++){
			cout<<str2[i];
		}
		cout<<endl;
		
	}
	return 0;
} 
2023/10/20 20:10
加载中...