这道题的题面就不介绍了，题意也懒得解释了。

我们有一个小技巧，可以找到当前数字下一个正好等于自己的位置。

c[0]=-1;
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    if(b[a[i]])c[b[a[i]]]=i,c[i]=b[a[i]];
    else b[a[i]]=i;
}

很好，现在我们珂以进入正题。

0.约定

#define pf pop_front
#define pb pop_back
#define insert push_back
#define l 'L'
#define r 'R'
//命名空间就省略了
int T,n,a[N],val[N];
int q1[N],q2[N];
int l1,r1,l2,r2,b[N],c[N];
bool vis[N],flg;
char ans[N];
void csh(){
    flg=0;
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    c[0]=-1;
}

1.解决问题

小技巧:

c[0]=-1;
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    if(b[a[i]])c[b[a[i]]]=i,c[i]=b[a[i]];
    else b[a[i]]=i;
}

核心:

bool solve(char fifi){
    deque<int>q1,q2;
    string ah,at;
    ah="",at="";
    ah=ah+fifi;
    at=at+l;
    if(fifi==l){
        for(int i=2;i<c[1];i++)q1.insert(i);
        for(int i=n;i>c[1];i--)q2.insert(i);
    }else{
        for(int i=1;i<c[n];i++)q1.insert(i);
        for(int i=n-1;i>c[n];i--)q2.insert(i);
    }
    while(!q1.empty()||!q2.empty()){
        int q=q1.size()?q1.front():0;
        int w=q2.size()?q2.front():0;
        int e=q1.size()?q1.back():0;
        int t=q2.size()?q2.back():0;
        if(c[q]==e){
            ah+=l,at+=l;
            q1.pf();q1.pb();
        }else if(c[q]==t){
            ah+=l,at+=r;
            q1.pf(),q2.pb();
        }else if(c[w]==e){
            ah+=r,at+=l;
            q2.pf(),q1.pb();
        }else if(c[w]==t){
            ah+=r,at+=r;
            q2.pf(),q2.pb();
        }else return 0;
    }
    reverse(at.begin(),at.end());
    ah+=at;
    cout<<ah<<endl;
    return 1;
}

string ah,at;
ah="",at="";
ah=ah+fifi;//第一个
at=at+l;//为了字典序最小，剩下的最后一个绝对L
if(fifi==l){//如果第一个是L，说明第一个已经有着落了，以C[1]为分界线扫描
    for(int i=2;i<c[1];i++)q1.insert(i);
    for(int i=n;i>c[1];i--)q2.insert(i);
}else{//同理，第n个有着落了，于是以C[n]为分界线扫描
    for(int i=1;i<c[n];i++)q1.insert(i);
    for(int i=n-1;i>c[n];i--)q2.insert(i);
}
//q1为第一次出现的，q2为第二次出现的

处理字符串:

while(!q1.empty()||!q2.empty()){
    int q=q1.size()?q1.front():0;//俩队列的队首队尾全部弹出。
    int w=q2.size()?q2.front():0;
    int e=q1.size()?q1.back():0;
    int t=q2.size()?q2.back():0;
    if(c[q]==e){ah+=l,at+=l;q1.pf();q1.pb();}
    //如果当前LL情况正好匹配，那么把LL加入情况；
    else if(c[q]==t){ah+=l,at+=r;q1.pf(),q2.pb();}
    //如果当前LR情况正好匹配，那么把LR加入情况；
    else if(c[w]==e){ah+=r,at+=l;q2.pf(),q1.pb();}
    //如果当前RL情况正好匹配，那么把RL加入情况；
    else if(c[w]==t){ah+=r,at+=r;q2.pf(),q2.pb();}
    //如果当前RR情况正好匹配，那么把RR加入情况；
    else return 0;
    //如果鸟都不匹配，那么返回不成立
}

处理答案:

reverse(at.begin(),at.end());
ah+=at;
cout<<ah<<endl;
return 1;

后面那一半全部要翻转处理因为：

for(int i=n;i>c[1];i--)q2.insert(i);

for(int i=n-1;i>c[n];i--)q2.insert(i);

是反向的。

于是这道题就完美地被解决了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<deque>
#define N 1919810
#define pf pop_front
#define pb pop_back
#define insert push_back
#define l 'L'
#define r 'R'
using namespace std;
int T,n,a[N],val[N];
int q1[N],q2[N];
int l1,r1,l2,r2,b[N],c[N];
bool vis[N],flg;
char ans[N];
void csh(){
    flg=0;
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    c[0]=-1;
}
bool solve(char fifi){
    deque<int>q1,q2;
    string ah,at;
    ah="",at="";
    ah=ah+fifi;
    at=at+l;
    if(fifi==l){
        for(int i=2;i<c[1];i++)q1.insert(i);
        for(int i=n;i>c[1];i--)q2.insert(i);
    }else{
        for(int i=1;i<c[n];i++)q1.insert(i);
        for(int i=n-1;i>c[n];i--)q2.insert(i);
    }
    while(!q1.empty()||!q2.empty()){
        int q=q1.size()?q1.front():0;
        int w=q2.size()?q2.front():0;
        int e=q1.size()?q1.back():0;
        int t=q2.size()?q2.back():0;
        if(c[q]==e){ah+=l,at+=l;q1.pf();q1.pb();}
        else if(c[q]==t){ah+=l,at+=r;q1.pf(),q2.pb();}
        else if(c[w]==e){ah+=r,at+=l;q2.pf(),q1.pb();}
        else if(c[w]==t){ah+=r,at+=r;q2.pf(),q2.pb();}
        else return 0;
    }
    reverse(at.begin(),at.end());
    ah+=at;
    cout<<ah<<endl;
    return 1;
}
signed main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        n=n<<1;
        csh();
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(b[a[i]])c[b[a[i]]]=i,c[i]=b[a[i]];
            else b[a[i]]=i;
        }
        if(!solve(l)&&!solve(r))puts("-1");
    }
    return 0;
}