问题 C: [CSP-S 2021] 回文
传统题
1.000s
时间限制
512MB
内存限制
7 提交
1 解决
【题目描述】
## 题目描述
给定正整数 n 和整数序列 a1, a2, ..., a2n，在这 2n 个数中，1, 2, ..., n 分别各出现恰好 2 次。现在进行 2n 次操作，目标是创建一个长度同样为 2n 的序列 b1, b2, ..., b2n，初始时 b 为空序列，每次可以进行以下两种操作之一：
1. 将序列 a 的开头元素加到 b 的末尾，并从 a 中移除。
2. 将序列 a 的末尾元素加到 b 的末尾，并从 a 中移除。
我们的目的是让 b 成为一个**回文数列**，即令其满足对所有 1≤ i≤ n，有 bi = b2 n + 1 - i。请你判断该目的是否能达成，如果可以，请输出字典序最小的操作方案，具体在【输出格式】中说明。
## 输入格式
每个测试点包含多组测试数据。
输入的第一行，包含一个整数 T，表示测试数据的组数。对于每组测试数据：
第一行，包含一个正整数 n。
第二行，包含 2n 个用空格隔开的整数 a1, a2, ..., a2n。
## 输出格式
对每组测试数据输出一行答案。
如果无法生成出回文数列，输出一行 ‐1，否则输出一行一个长度为 2n 的、由字符 L 或 R 构成的字符串（不含空格），其中 L 表示移除开头元素的操作 1，R 表示操作 2。
你需要输出所有方案对应的字符串中字典序最小的一个。
字典序的比较规则如下：长度均为 2n 的字符串 s1~2n 比 t1~2n字典序小，当且仅当存在下标 1≤ k≤ 2n 使得对于每个 1≤ i < k 有 si = ti 且 sk < tk。
## 样例 #1
### 样例输入 #1
2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
### 样例输出 #1
LRRLLRRRRL
-1
## 样例 #2
### 样例输入 #2
见附件中的 palin/palin2.in
### 样例输出 #2
见附件中的 palin/palin2.ans
## 提示
**【样例解释 #1】**
在第一组数据中，生成的的 b 数列是 [4, 5, 3, 1, 2, 2, 1, 3, 5, 4]，可以看出这是一个回文数列。
另一种可能的操作方案是 LRRLLRRRRR，但比答案方案的字典序要大。
**【数据范围】**
令 Σn$ 表示所有 T 组测试数据中 n 的和。
对所有测试点保证 1≤ T≤ 100，1≤ n, Σn≤ 5×105。
测试点编号
|
T≤
|
n≤
|
Σn≤
|
特殊性质
|
1~7
|
10
|
10
|
50
|
无
|
8~10
|
100
|
20
|
1000
|
无
|
11~12
|
100
|
100
|
1000
|
无
|
13~15
|
100
|
1000
|
25000
|
无
|
16~17
|
1
|
5×105
|
5×105
|
无
|
18~20
|
100
|
5×105
|
5×105
|
有
|
21~25
|
100
|
5×105
|
5×105
|
无
|
特殊性质：如果我们每次删除 a 中两个相邻且相等的数，存在一种方式将序列删空（例如 a = [1, 2, 2, 1]）。