P7915 [CSP-S 2021] 回文

暴力设为区间的是否合法

直接记搜，考虑当前决策只有三种匹配方式，记搜即可

区间就考虑端点和端点匹配，端点和区间内匹配

考虑第一步选择的情况

则序列可以划分成两个子问题

vxxxxxxvxxxx ，两个把序列分成了两份，因为剩下一个必须最后弹出

记左边一半为，右边一半为

第二次操作和倒数第二次操作移走的数必须相同，第二次操作为，倒数第二次操作为

我们发现弹出一定只能发生在这四种之间，用双端队列维护

#include<bits/stdc++.h>
#define pt putchar(' ')
#define nl puts("")
#define pi pair<int,int>
#define pb push_back
#define go(it) for(auto &it:as[x])
using namespace std;

const int N=1e6+10;
int n;
int a[N];
char c[N];

int fr(){
    int x=0,flag=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*flag;
}
void fw(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) fw(x/10);
    putchar(x%10+'0');
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}

bool check(int l1,int r1,int l2,int r2)
{
    int idx=1;
    while(idx<n/2)
    {
        if(l1<r1 && a[l1]==a[r1])
        {
            l1++,r1--;
            c[++idx]='L',c[n-idx+1]='L';
        }
        else if(l1<=r1 && l2<=r2 && a[l1]==a[l2])
        {
            l1++,l2++;
            c[++idx]='L',c[n-idx+1]='R';
        }
        else if(l1<=r1 && l2<=r2 && a[r1]==a[r2])
        {
            r1--,r2--;
            c[++idx]='R',c[n-idx+1]='L';
        }
        else if(l2<r2 && a[l2]==a[r2])
        {
            l2++,r2--;
            c[++idx]='R',c[n-idx+1]='R';
        }
        else return 0;
    }
    return 1;
}

void solve()
{
    memset(c,0,sizeof c);
    n=fr()<<1;
    for(int i=1;i<=n;i++) a[i]=fr();
    int p=2;
    while(a[p]!=a[1]) p++;
    c[1]=c[n]='L';
    if(check(2,p-1,p+1,n)) {printf("%s\n",c+1);return;}
    p=n-1;
    while(a[p]!=a[n]) p--;
    c[1]='R',c[n]='L';
    if(check(1,p-1,p+1,n-1)) {printf("%s\n",c+1);return;}
    puts("-1");
}

int main()
{
    int T=fr();
    while(T--) solve();

    return 0;
}