Palindrome (csp-s-2021-palin) solution

Old rules , Present a topic ：

---

Title Description

Given a positive integer  n  Sum integer sequence a1​,a2​,…,a2n​, Here  2 n2n  In number , n1,2,…,n  Each appears exactly  2  Time . For now 2n  operations , The goal is to create a length of  2n  Sequence b1​,b2​,…,b2n​, At the beginning  b  Empty sequence , You can do one of the following two operations at a time ：

1. The sequence of  a  The beginning element of is added to  b  At the end of , And from  a  Remove .
2. The sequence of  a  The end element of is added to  b  At the end of , And from  a  Remove .

Our aim is to make  b  Become a Palindrome sequence , Even if it meets all 1≤i≤n, Yes bi​=b2n+1−i​. Please judge whether the goal can be achieved , If possible , Please output the operation scheme with the smallest dictionary order

Input format

Each test point contains multiple sets of test data .

The first line of input , Contains an integer  T, Number of groups representing test data . For each group of test data ：

first line , Contains a positive integer  n.
The second line , contain 2n  Integers separated by spaces a1​,a2​,…,a2n​.

Output format

Output a line of answers to each group of test data .

If the palindrome sequence cannot be generated , Output one line  ‐1, Otherwise, output a line with a length of  2n  Of 、 By the character  L  or  R  The string formed （ No spaces ）, among  L  Indicates the operation of removing the starting element 1,R  Presentation operation 2.

You need to output the string with the smallest lexicographic order among all the schemes .

The comparison rules of dictionary order are as follows ： The length is  2 n  String s 1∼2n​  Than t 1∼2n​  The dictionary order is small , If and only if there is a subscript 1≤k≤2n  So that for each  1≤i<k  Yes si​=ti​  And sk​<tk​.

I/o sample

Input #1

2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3

Output #1

LRRLLRRRRL
-1

---

Answer key ：

According to the meaning :

Let's be clear first ： Try not to choose the right if you can choose the left , Because the question requires the output of a set of answers with the smallest dictionary order ,L Definitely prior to R;

secondly , If it can constitute b Array words , Then the last character of the output answer must be 'L', I don't need to talk about this , Because there is only one character at the end of the selection , We can take it as the left , It can also be regarded as the right . Then we must choose the left , In this way, the dictionary order is as small as possible .

Treat this problem , We still have 2 Methods ：

Ashes class practice ： I cite all possible situations (O(2^N)), I don't need to say that you know you must TEL Dropped , We'll just ignore this mindless method

wonderful ： We can start both inside and outside ：

Start first , We have two situations —— Choose the leftmost or rightmost , We prefer the leftmost , If the left side is not good, then consider the right side .

Let's take the left as an example to discuss （ The ideas on the right and left are exactly the same , No more tiring ）>>>>

Given a length of 2n Sequence N, Build array S Express our answer , from ’‘L’R‘ form ; The leftmost part of the sequence waileft, The rightmost side of the array is marked wairight

In the initial state , Outer layer waileft Subscript to be 1,wairight Subscript to be 2n

We set the leftmost number as X, Take out X; Then find out the relation with X Equal value , Note that their subscripts are i1,i2, remember i2 The number on the left is neileft,i2 The number on the right is recorded as neiright

Take out X after , Outer layer left The subscript becomes i1+1, On the right right Unchanged or 2n

Next, we will start work on both sides at the same time , How to start ？

After the above operation , We have found a connection with X Subscript of equal value . Because what we finally get is the palindrome sequence , Then this palindrome sequence is read from left to right or from right to left , The order is the same , It's easy to know , Both ends of the final palindrome sequence are X, Then the palindrome sequence is approaching X A set of equal values of must be on the leftmost side of the outer layer in the original sequence waileft Or the rightmost wairight, A subscript is i2 To the left or right of (neileft or neiright).

Well , There are four situations ：

1.        N[waileft]=N[neileft]

2.        N[waileft]=N[neiright]

3.        N[wairight]=N[neileft]

4         N[wairight]=N[neiright]

Be careful ： The order of these four cases is not random , It must be rigorous . Why do you say that ？

Because the above four situations are 4 Kind of operation ：

Meet the corresponding situation , We will carry out the corresponding operation

1.            L L

2.            L R

3.             R L

4.             R R

We are still We should follow the principle of minimum dictionary order

What if the four situations are not satisfied ？ That means this situation is not tenable . We have to choose the rightmost again , If not , That means this sequence cannot form palindromes , Decisive output -1, End procedure . This is a misunderstanding of judgment , The key point of reducing redundant operations ！

In this way, we can make a judgment at the same time S A value at both ends of the array , Keep filling in the blanks .

How to fill in ？

First choose the left side S[1]=L  ,S[2n]=L

If you choose the right               S[1]=R  ,S[2n]=L

Whether it's the outer layer or the inner layer , Just choose the left (waileft or neileft), We all remember it as L;

Just choose the right (wairight or neiright), We all remember it as R

Fill in from both sides , In this way, if it can fill , It must be the right answer .

The complete code is as follows

Code(100 ptx)

#include<cstdio>
int num[1000005];
char s[1000005];
int tot,t;
int main(){
	scanf("%d",&tot);
	while(tot--){
		scanf("%d",&t);
		int sum=2*t,nei;
		for(int i=1;i<=sum;i++)
			scanf("%d",&num[i]);
		for(int i=2;i<=sum;i++){
			if(num[1]==num[i]){
				nei=i;
				break;
			}
	    }
	    int wai_left=2,wai_right=sum,nei_left=nei-1,nei_right=nei+1;
        int start=1,end=sum;
	    s[start]='L';s[end]='L';
	    while(1){
	    	if(start==end-1){
	    		s[sum+1]='\0';
	    		printf("%s\n",s+1);
	    		break;
			}
	        if(num[wai_left]==num[nei_left] && wai_left<nei_left){
	        	s[++start]='L';s[--end]='L';
	         	wai_left++;nei_left--;
			}
			else if(num[wai_left]==num[nei_right] ){
			 	s[++start]='L';s[--end]='R';
	         	wai_left++;nei_right++;
			}
			else if(num[wai_right]==num[nei_left]){
				s[++start]='R';s[--end]='L';
	         	wai_right--;nei_left--;
			}
			else if(num[wai_right]==num[nei_right]  &&  wai_right>nei_right){
				s[++start]='R';s[--end]='R';
				wai_right--;nei_right++;
			}
			else break;
		}	
		if(start==end-1)continue;
		for(int i=1;i<sum;i++){
			if(num[sum]==num[i]){
				nei=i;
				break;
			}
	    }
	    wai_left=1;wai_right=sum-1;nei_left=nei-1;nei_right=nei+1;
	    start=1,end=sum;
	    s[start]='R';s[end]='L';
	    while(1){
	    	if(start==end-1){
	    		s[sum+1]='\0';
	    		printf("%s\n",s+1);
	    		break;
			}
	        if(num[wai_left]==num[nei_left] && wai_left<nei_left){
	        	s[++start]='L';s[--end]='L';
	            wai_left++;nei_left--;
			}
			else if(num[wai_left]==num[nei_right]){
			 	s[++start]='L';s[--end]='R';
	         	wai_left++;nei_right++;
			}
			else if(num[wai_right]==num[nei_left]){
				s[++start]='R';s[--end]='L';
	         	wai_right--;nei_left--;
			}
			else if(num[wai_right]==num[nei_right] && wai_right>nei_right){
				s[++start]='R';s[--end]='R';
	         	wai_right--;nei_right++;
			}
			else{
				putchar('-');putchar('1');putchar('\n');
				break;
			}
		}			
	}
	return 0;
} 

The program evaluation results are as follows ：

But the code when I first submitted is as follows ：

Code(first) 

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=500005;
int n;
int a[maxn*2];
char res[maxn*2];
bool work(int l1,int r1,int l2,int r2)
	{
	for(int i=1;i<n;i++)
		{
		if((l1<=r1)&&(((l2<=r2)&&(a[l1]==a[l2]))||((l1<r1)&&(a[l1]==a[r1]))))
			{
			if((l1<r1)&&(a[l1]==a[r1]))
				{
				l1++;
				r1--;
				res[i]='L';
				res[2*(n-1)-i+1]='L';
				}
			else
				{
				l1++;
				l2++;
				res[i]='L';
				res[2*(n-1)-i+1]='R';
				}
			}
		else if((l2<=r2)&&(((l1<=r1)&&(a[r2]==a[r1]))||((l2<r2)&&(a[l2]==a[r2]))))
			{
			if((l2<r2)&&(a[l2]==a[r2]))
				{
				l2++;
				r2--;
				res[i]='R';
				res[2*(n-1)-i+1]='R';
				}
			else
				{
				r1--;
				r2--;
				res[i]='R';
				res[2*(n-1)-i+1]='L';
				}
			}
		else
			{
			return false;
			}
		}
	return true;
	}
int main()
	{
	int t;
	cin>>t;
	while(t--)
		{
		cin>>n;
		for(int i=1;i<=2*n;i++)
			{
			scanf("%d",&a[i]);
			}
		int l1=0;
		int l2=0;
		for(int i=2;i<=2*n;i++)
			{
			if(a[i]==a[1])
				{
				l1=i;
				break;
				}
			}
		for(int i=1;i<2*n;i++)
			{
			if(a[i]==a[2*n])
				{
				l2=i;
				break;
				}
			}
		if(work(2,l1-1,l1+1,2*n))
			{
			printf("L%sL",res+1);
			cout<<endl;
			}
		else if(work(1,l2-1,l2+1,2*n-1))
			{
			printf("R%sL",res+1);
			cout<<endl;
			}
		else
			{
			cout<<"-1"<<endl;
			}
		}
	return 0;
	}

The evaluation results are as follows ：

  I was cheated for more than half an hour . Readers can compare the differences between the two codes . Just add two more lines

s[sum+1]='\0';

Otherwise, the residual term of the previous result may be output , You must have a closing symbol ！ It sounds an alarm for you .....

End~~~~

If there is something you don't understand , Welcome to consult below the comments .

Writing is not easy to , Thank you for your support ！