求助,大数据过了,小数据没过
查看原帖
求助,大数据过了,小数据没过
215698
miker楼主2021/10/28 18:06

RT

#include<bits/stdc++.h>
using namespace std;
const int N=1000002;
int n,tt;
int h[N];
int l,r,s,t,l1,l2;
bool ans1[N/2],ans2[N/2];
bool fin;
void dfs(){
	if(l1==n-1&&l2==n-1){
		int ll=1,rr=2*n;
		for(int i=1;i<=n-1;i++)
		if(ans1[i]) {printf("L");ll++;}
		else {printf("R");rr--;}
		if(h[ll]==h[rr]) printf("LR");
		else if(h[ll]==h[ll+1]) printf("LL");
		else printf("RR");
		for(int i=n-1;i>=1;i--)
		if(ans2[i]) printf("L");
		else printf("R");
		printf("\n");
		fin=1;
		return ;
	}
	l1++,l2++;
	if(h[l]==h[s]&&l<s){
		l++;s--;
		ans1[l1]=ans2[l2]=1;
		dfs();
		l--;s++;
	}
	else if(h[l]==h[t]&&l<t){
		l++;t++;
		ans1[l1]=1;ans2[l2]=0;
		dfs();
		l--;t++;
	}
	else if(h[r]==h[s]&&r>s){
		r--;s--;
		ans1[l1]=0;ans2[l2]=1;
		dfs();
		r++;s++;
	}
	else if(h[r]==h[t]&&r>t){
		r--;t++;
		ans1[l1]=0;ans2[l2]=0;
		dfs();
		r++;t--;
	}
	l1--;
	l2--;
	return ;
}
int main(){
//	freopen("palin.in","r",stdin);
//	freopen("palin.out","w",stdout);
	scanf("%d",&tt);
	while(tt--){
		fin=0;
		scanf("%d",&n);
		for(int i=1;i<=2*n;i++)
			scanf("%d",&h[i]);
		
		l1=l2=1;
		ans1[1]=ans2[1]=1;
		l=2;r=2*n;
		for(int i=2;i<=n*2;i++)
		if(h[i]==h[1]){
			s=i-1;
			t=i+1;
			break;
		}
		dfs();
		if(fin) continue;
		
		l1=l2=1;
		fill(ans1+1,ans1+1+n,0);
		fill(ans2+1,ans2+1+n,0);
		ans1[1]=0;ans2[1]=1;
		l=1;r=2*n-1;
		for(int i=1;i<=n*2-1;i++)
		if(h[i]==h[n*2]){
			s=i-1;
			t=i+1;
			break;
		}
		dfs();
		if(!fin)printf("-1\n");
	}
	return 0;
}
2021/10/28 18:06
加载中...