记录编号	608488	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	3621.[CSP 2021S]回文	最终得分	100
用户昵称	窝法氦镁烷	是否通过	通过
代码语言	C++	运行时间	1.731 s
提交时间	2025-10-26 15:39:19	内存使用	8.56 MiB

#include <bits/stdc++.h> 
using namespace std;
 
const int N = 5e5 + 10;
 int n; int a[N * 2]; char c[N * 2];
 
// [L.....l-1    r+1....R]生成回文串
 bool dfs(int L, int R, int l, int r)
  {    if(L == l && r == R) 
  return true;    
  int ls = 2 * n - (R - L), rs = R - L + 1;   
   if(L < l - 1 && a[L] == a[l - 1])   //LL
    {        c[ls] = 'L'; c[rs] = 'L';      
	  return dfs(L + 1, R, l - 1, r);    
	  }    
	  else 
	  if(r + 1 <= R && a[L] == a[r + 1])   // LR和LL不可能同时出现   
	   {        c[ls] = 'L'; c[rs] = 'R';        
	   return dfs(L + 1, R, l, r + 1);    
	   }    else
	    if(L <= l - 1 &&  a[l - 1] == a[R])  // RL 如果存在多解 选左边<=>选右边    
		{        c[ls] = 'R'; c[rs] = 'L';        
		return dfs(L, R - 1, l - 1, r);    }    
		else
		 if(R > r + 1 && a[r + 1] == a[R])  // RR和RL不可能同时出现   
		  {        c[ls] = 'R'; c[rs] = 'R';       
		   return dfs(L, R - 1, l, r + 1);    }    
		   return false; }
 
void work()
 {    memset(a, 0, sizeof(a));  
   memset(c, 0, sizeof(c));   
    scanf("%d", &n);    
	for(int i = 1; i <= 2 * n; ++i) scanf("%d", &a[i]);    // 第一次选择左    
	int x = 0; 
	for(int i = 2; i <= 2 * n; ++i) 
	if(a[i] == a[1]) 
	{ x = i; break; }   
	 c[1] = 'L'; c[2 * n] = 'L';  
	   if(dfs(2, 2 * n, x, x)) 
	   { puts(c + 1); return; }    // 第一次选择右    
	   x = 0;    
	   for(int i = 1; i <= 2 * n - 1; ++i) 
	   if(a[i] == a[2 * n]) { x = i; break; }   
	    c[1] = 'R'; c[2 * n] = 'L';   
		 if(dfs(1, 2 * n - 1, x, x))
		  { puts(c + 1); return; }   
		   puts("-1"); }
		   int main() 
		   {    
		   freopen("2021palin.in","r",stdin);
	freopen("2021palin.out","w",stdout);int T; scanf("%d", &T);   
		    while(T--) work();    
			return 0; 
			}