P7915 [CSP-S 2021] 回文

用户头像 发布于 19 小时前 10 次阅读 OI

P7915 [CSP-S 2021] 回文

先考虑第一个选 L 的情况，第一个选 R 的情况是同理的。

找到与 a1a_1 相等的数 axa_x，把 [2,x)[2,x) 和 (x,2n](x,2n] 看成两个双端队列，

按照字典序分类讨论，每次取两个队列的一个顶部和一个底部，

然后往答案字符串两边加字符即可。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5;
int T,n;
int a[N];

string solve(){
	deque<int> s1,s2;
	string ans="L";
	for(int i=1;i<=2*n-2;i++) ans+=" ";
	ans+="L";
	int x=a[1],y,idx=1;
	for(int i=2;i<=2*n;i++) if(a[i]==x){
		y=i;
		break;
	}
	for(int i=2;i<y;i++) s1.push_back(a[i]);
	for(int i=y+1;i<=2*n;i++) s2.push_front(a[i]);
	int l=0,r=2*n-1;
	while(s1.size()||s2.size()){
		if(s1.size()>1&&s1.front()==s1.back()){
			ans[++l]='L',ans[--r]='L';
			s1.pop_front(),s1.pop_back();
		}
		else if(s1.size()&&s2.size()&&s1.front()==s2.back()){
			ans[++l]='L',ans[--r]='R';
			s1.pop_front(),s2.pop_back();
		}
		else if(s1.size()&&s2.size()&&s2.front()==s1.back()){
			ans[++l]='R',ans[--r]='L';
			s2.pop_front(),s1.pop_back();
		}
		else if(s2.size()>1&&s2.front()==s2.back()){
			ans[++l]='R',ans[--r]='R';
			s2.pop_front(),s2.pop_back();
		}
		else return "-1";
	}
	return ans;
}

string solve2(){
	deque<int> s1,s2;
	string ans="R";
	for(int i=1;i<=2*n-2;i++) ans+=" ";
	ans+="L";
	int x=a[2*n],y,idx=1;
	for(int i=1;i<2*n;i++) if(a[i]==x){
		y=i;
		break;
	}
	for(int i=1;i<y;i++) s1.push_back(a[i]);
	for(int i=y+1;i<2*n;i++) s2.push_front(a[i]);
	int l=0,r=2*n-1;
	while(s1.size()||s2.size()){
		if(s1.size()>1&&s1.front()==s1.back()){
			ans[++l]='L',ans[--r]='L';
			s1.pop_front(),s1.pop_back();
		}
		else if(s1.size()&&s2.size()&&s1.front()==s2.back()){
			ans[++l]='L',ans[--r]='R';
			s1.pop_front(),s2.pop_back();
		}
		else if(s1.size()&&s2.size()&&s2.front()==s1.back()){
			ans[++l]='R',ans[--r]='L';
			s2.pop_front(),s1.pop_back();
		}
		else if(s2.size()>1&&s2.front()==s2.back()){
			ans[++l]='R',ans[--r]='R';
			s2.pop_front(),s2.pop_back();
		}
		else return "-1";
	}
	return ans;
}

signed main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=2*n;i++) cin>>a[i];
		string ans=solve();
		if(ans!="-1"){
			cout<<ans<<"\n";
			continue;
		}
		ans=solve2();
		cout<<ans<<"\n";
	}
	return 0;
}