暴力56分,能优化吗
查看原帖
暴力56分,能优化吗
1034206
lusq楼主2024/1/26 17:25
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
bool hw(int l,int r){
	for(int i=l;i<(l+r+1)/2;i++){
		if(a[i]!=a[r-(i-l)]){
			return 0;
		}
	}
	return 1;
}
string dfs(int l,int r,int zl,int zr){
	string st="";
	if(zl==l && zr==r){
		return st;
	}
	if(zr==r){
		if(hw(l,zl-1)){
			for(int i=l;i<zl;i++){
				st+="L";
			}
			return st;
		}else{
			return "no";
		}
	}
	if(zl==l){
		if(hw(zr+1,r)){
			for(int i=zr;i<r;i++){
				st+="R";
			}
			return st;
		}else{
			return "no";
		}
	}
	int li=r,ri=l;
	for(int i=l+1;i<r;i++){
		if(a[i]==a[l]){
			li=i;
		}
		if(a[i]==a[r]){
			ri=i;
		}
	}
	if(li==zl-1){
		st=dfs(l+1,r,zl-1,zr);
		if(st!="no"){
			return "L"+st+"L";
		}
	}
	if(li==zr+1){
		st=dfs(l+1,r,zl,zr+1);
		if(st!="no"){
			return "L"+st+"R";
		}
	}
	if(ri==zl-1){
		st=dfs(l,r-1,zl-1,zr);
		if(st!="no"){
			return "R"+st+"L";
		}
	}
	if(ri==zr+1){
		st=dfs(l,r-1,zl,zr+1);
		if(st!="no"){
			return "R"+st+"R";
		}
	}
	return "no";
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=0;i<n*2;i++){
			scanf("%d",&a[i]);
		}
		int l=0,r=0;
		for(int i=1;i<n*2-1;i++){
			if(a[i]==a[0]){
				l=i;
			}
			if(a[i]==a[n*2-1]){
				r=i;
			}
		}
		if(l==0){
			if(hw(0,n*2-1)){
				for(int i=0;i<2*n;i++){
					cout<<'L';
				}
				cout<<endl;
			}else{
				cout<<-1<<endl;
			}
		}else{
			string st=dfs(1,n*2-1,l,l);
			if(st!="no"){
				cout<<"L"+st+"L"<<endl;
			}else{
				st=dfs(0,n*2-2,r,r);
				if(st=="no"){
					cout<<-1<<endl;
				}else{
					cout<<"R"+st+"L"<<endl;
				}
			}
		}
	}
 	return 0;
}


2024/1/26 17:25
加载中...