暴力 $dp$ 设 $f_{l,r}$ 为区间 $[l,r]$ 的是否合法
直接记搜，考虑当前决策只有 $(l,r),(l,l’)[a_l=a_{l’}],(r’,r)[a{r’}=a_r]$ 三种匹配方式，记搜即可
区间 $dp$ 就考虑端点和端点匹配，端点和区间内匹配
考虑第一步选择 $L$ 的情况
则序列可以划分成两个子问题
vxxxxxxvxxxx $a_1=v$，两个 $v$ 把序列分成了两份，因为剩下一个 $v$ 必须最后弹出
记左边一半 $x$ 为 $(l_1,r_1)$，右边一半 $x$ 为 $(l_2,r_2)$
第二次操作和倒数第二次操作移走的数必须相同，第二次操作为 $l_1/r_2$，倒数第二次操作为 $r_1/l_2$
我们发现弹出一定只能发生在 $(l_1,r_1),(l_2,r_2),(l_1,r_2),(r_2,r_1)$ 这四种之间，用双端队列维护
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #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;
}
|
