2785. T3-[CSP-S 2021] 回文palindrome
时间限制：1000 MS 内存限制：128 MB
题目描述
## 题目描述 给定正整数$ n$ 和整数序列$ a1,a2,...,a2n$，在这 $2n$个数中，$1,2,...,n$ 分别各出现恰好$ 2$次。 现在进行 $2n$ 次操作，目标是创建一个长度同样为$ 2n$ 的序列 4b1,b2,...,b2n$，初始时$ b$ 为空序列，每次可以进行以下两种操作之一： 1. 将序列 $a$ 的开头元素加到$ b$ 的末尾，并从 $a$ 中移除 2. 将序列 $a$的末尾元素加到$ b$的末尾，并从 $a$ 中移除 我们的目的是让 $b$ 成为一个回文数列，即令其满足对所有$ 1\lei\len$，有$ bi=b2n+1-i$。 请你判断该目的是否能达成，如果可以，请输出字典序最小的操作方案，具体在【输出格式】中说明。 ## 输入格式 每个测试点包含多组测试数据。 输入的第一行包含一个整数 $T$，表示测试数据的组数。 每组测试数据的第一行包含一个正整数$ n$，第二行包含 $2n$ 个用空格隔开的整数 $a1,a2,...,a2n$。 ## 输出格式 对每个测试数据输出一行答案。 如果无法生成出回文数列，输出一行 $‐1$，否则输出一行一个长度为$ 2n$ 的、由字符$ `L$` 或 $`R$` 构成的字符串（不含空格），其中 `L` 表示移除开头元素的操作 $1$，$`R$` 表示操作 $2$。 你需要输出所有方案对应的字符串中字典序最小的一个。 字典序的比较规则如下：长度均为 $2n$的字符串$ s1..2n$比$ t1..2n$ 字典序小，当且仅当存在下标$ 1\lek\le2n$ 使得 $\forall1\lei<k$ 有 $si=ti$ 且$ sk<tk$。 ## 数据范围 令$ \sumn$ 表示所有 $$ 组测试数据中 $n$的和。 对所有测试点保证$ 1\leT\le100,1\len,\sumn\le5\times105$。  特殊性质：如果我们每次删除 $a$ 中两个相邻且相等的数，存在一种方式将序列删空（例如 $a=[1,2,2,1]$）。 ```in4 2 5 4 1 2 4 5 3 1 2 3 5 3 3 2 1 2 1 3 ``` ```out4 LRRLLRRRRL -1 ``` ## 说明 在第一组数据中，生成的的 $b$ 数列是 $`4 5 3 1 2 2 1 3 5 4$`，可以看出这是一个回文数列。 另一种可能的操作方案是$ `LRRLLRRRRR$`，但比答案方案的字典序要大。