求解!!!
查看原帖
求解!!!
640477
biophitma_wby楼主2024/10/12 21:36
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int t,n,a[N];
int c[N],head_c=0,rear_c=0,d[N],head_d=0,rear_d=0;
bool ans[N];int len=0;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout); 
	scanf("%d",&t);
	while(t--){
		memset(ans,0,sizeof(ans));
		memset(c,-1,sizeof(c));
		memset(d,-1,sizeof(d));
		head_c=rear_c=head_d=rear_d=len=0;
		scanf("%d%d",&n,&a[1]);
		int x;
		for(int i=2;i<=2*n;i++){
			scanf("%d",&a[i]);
			if(a[i]==a[1]){
				x=i;
			}
		}
		//cout<<x<<endl;
		for(int i=2;i<=x-1;i++){
			rear_c++;
			c[rear_c]=a[i];
			//cout<<a[i]<<" ";
		}
		//cout<<endl;
		for(int i=2*n;i>=x+1;i--){
			rear_d++;
			d[rear_d]=a[i];
			//cout<<a[i]<<" ";
		}
		//cout<<endl;
		len++;ans[len]=0;
		bool isTrue=true;
		head_c=head_d=1;
		while(head_c<=rear_c||head_d<=rear_d){
			int c_tmp_head=c[head_c],d_tmp_head=d[head_d];
			int c_tmp_rear=c[rear_c],d_tmp_rear=d[rear_d];
			//printf("%d %d %d %d\n",head_c,rear_c,head_d,rear_d);
			if(head_c==rear_c||head_c>rear_c)c_tmp_rear=-1;
			if(head_d==rear_d||head_d>rear_d)d_tmp_rear=-1;
			//printf("%d %d %d %d\n",c_tmp_head,c_tmp_rear,d_tmp_head,d_tmp_rear);
			if(c_tmp_head==c_tmp_rear&&(c_tmp_head!=-1||c_tmp_rear!=-1)){
				++len;
				ans[len]=0;
				ans[2*n-len+1]=0;
				head_c++;rear_c--;
			}else if(c_tmp_head==d_tmp_rear&&(c_tmp_head!=-1||d_tmp_rear!=-1)){
				++len;
				ans[len]=0;
				ans[2*n-len+1]=1;
				head_c++;rear_d--;
			}else if(d_tmp_head==c_tmp_rear&&(c_tmp_rear!=-1||d_tmp_head!=-1)){
				++len;
				ans[len]=1;
				ans[2*n-len+1]=0;
				rear_c--;head_d++;
			}else if(d_tmp_head==d_tmp_rear&&(d_tmp_head!=-1||d_tmp_rear!=-1)){
				++len;
				ans[len]=1;
				ans[2*n-len+1]=1;
				head_d++;rear_d--;
			}else{
				isTrue=false;
				break;
			}
			//cout<<len<<" "<<2*n-len+1<<endl;
		}
		if(isTrue==false){
			printf("-1\n");
			continue;
		}
		for(int i=1;i<=2*n-1;i++){
			if(ans[i]==0){
				printf("L");
			}else printf("R");
		}
		printf("L\n");
	}
	return 0;
}
2024/10/12 21:36
加载中...