40pts求教
查看原帖
40pts求教
48146
ezoiHY楼主2021/10/28 14:05
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int T,n,a[4000001],ltop,rtop,rbk,lbk;
char as[4000001];

bool solve(){
	for(int i=1;i<=n;i++){
		if(a[ltop]==a[lbk] and ltop<lbk){
			as[i]='L';
			as[(n<<1)-i+1]='L';
			ltop++;
			lbk--;
		}else if(a[ltop]==a[rbk] and ltop<=lbk and rtop>=rbk){
			as[i]='L';
			as[(n<<1)-i+1]='R';
			ltop++;
			rbk++;
		}else if(a[rtop]==a[lbk] and ltop<=lbk and rtop>=rbk){
			as[i]='R';
			as[(n<<1)-i+1]='L';
			rtop--;
			lbk--;
		}else if(a[rtop]==a[rbk] and rtop>rbk){
			as[i]='R';
			as[(n<<1)-i+1]='R';
			rtop--;
			rbk++;
		}else {
			return 0;
		}
	}
	return 1;
}

int main(){
//	freopen("palin2.in","r",stdin);
//	freopen("as.ans","w",stdout);
	scanf("%d",&T);
	while(T--){
		memset(as,0,sizeof(as));
		memset(a,0,sizeof(a));
		scanf("%d",&n);
		for(int i=1;i<=n<<1;i++){
			scanf("%d",&a[i]);
			if(i!=1 and a[i]==a[1]){
				lbk=i;
			}
		}
		ltop=1;
		rbk=lbk+1;
		rtop=n<<1;
		if(solve()){
			goto to1;
		}
		memset(as,0,sizeof(as));
		for(int i=n<<1-1;i;i--){
			if(a[i]==a[n<<1]){
				lbk=i;
				break;
			}
		}
		rbk=lbk+1;
		ltop=1;
		rtop=n<<1;
		if(solve()){
			to1:;
			printf("%s\n",as+1);
		}else{
			puts("-1");
		}
	}
	return 0;
}
2021/10/28 14:05
加载中...