P7915 求助 玄关!!!!QAQ
  • 板块学术版
  • 楼主____QAQ____
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/8/25 17:15
  • 上次更新2024/8/25 20:14:11
查看原帖
P7915 求助 玄关!!!!QAQ
1123756
____QAQ____楼主2024/8/25 17:15
#include<bits/stdc++.h>
using namespace std;
int l1,l2,r1,r2,T,n;
int arr[1000001];
int idx[1000001][2];
int need[500001];
string solu(bool flag) {
	string s="L";
	if(flag)s="R";
	int cnt=2*n-2;
	while(cnt) {
		int u=idx[arr[l1]][1];
		int v=idx[arr[r2]][0];
		if(u==r1||u==l2) {
			l1++;
			cnt-=2;
			s+="L";
			if(u==r1)r1--;
			if(u==l2)l2++;
		} else if(v==r1||v==l2) {
			r2--;
			cnt-=2;
			s+="R";
			if(v==r1)r1--;
			if(v==l2)l2++;
		} else {
			//无解
			s="";
			break;
		}
	}
	if(s.size()==0) {
		return s;
	}
	int lcnt=0,rcnt=0;
	for(int i=0; i<s.size(); i++) {
		if(s[i]=='L')need[i+1]=arr[++lcnt];
		else need[i+1]=arr[2*n-(++rcnt)+1];
	}
	int top=n;
	int l=lcnt+1,r=rcnt-1;
	while(top) {
		int want=need[top--];
		if(arr[l]==want) {
			l++;
			s+='L';
		} else {
			r--;
			s+='R';
		}
	}
	return s;
}
int main() {
	cin>>T;
	while(T--) {
		cin>>n;
		for(int i=1; i<=2*n; i++) {
			idx[i][0]=idx[i][1]=0;
		}
		for(int i=1; i<=2*n; i++) {
			cin>>arr[i];
			if(!idx[arr[i]][0])idx[arr[i]][0]=i;
			else idx[arr[i]][1]=i;
		}
		l1=2;
		l2=idx[arr[1]][1]+1;
		r1=idx[arr[1]][1]-1;
		r2=2*n;
		string ans=solu(0);
		if(ans.size()!=0)cout<<ans<<endl;
		else{
			l1=1,r1=idx[arr[2*n]][0]-1;
			l2=idx[arr[2*n]][0]+1,r2=n-1;
			ans=solu(1);
			if(ans.size()!=0)cout<<ans<<endl;
			else cout<<-1<<endl;
		}
	}
	return 0;
}
2024/8/25 17:15
加载中...