4559: [CSP-S 2021] 回文
Memory Limit:512 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:14
Solved:4
Description
[CSP-S 2021] 回文
题目描述
给定正整数 $n$ 和整数序列 $a_1, a_2, \ldots, a_{2 n}$,在这 $2 n$ 个数中,$1, 2, \ldots, n$ 分别各出现恰好 $2$ 次。现在进行 $2 n$ 次操作,目标是创建一个长度同样为 $2 n$ 的序列 $b_1, b_2, \ldots, b_{2 n}$,初始时 $b$ 为空序列,每次可以进行以下两种操作之一: 1. 将序列 $a$ 的开头元素加到 $b$ 的末尾,并从 $a$ 中移除。 2. 将序列 $a$ 的末尾元素加到 $b$ 的末尾,并从 $a$ 中移除。 我们的目的是让 $b$ 成为一个**回文数列**,即令其满足对所有 $1 \le i \le n$,有 $b_i = b_{2 n + 1 - i}$。请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在【**输出格式**】中说明。输入输出格式
输入格式
每个测试点包含多组测试数据。 输入的第一行,包含一个整数 $T$,表示测试数据的组数。对于每组测试数据: 第一行,包含一个正整数 $n$。 第二行,包含 $2 n$ 个用空格隔开的整数 $a_1, a_2, \ldots, a_{2 n}$。
输出格式
对每组测试数据输出一行答案。 如果无法生成出回文数列,输出一行 `‐1`,否则输出一行一个长度为 $2 n$ 的、由字符 `L` 或 `R` 构成的字符串(不含空格),其中 `L` 表示移除开头元素的操作 1,`R` 表示操作 2。 你需要输出所有方案对应的字符串中字典序最小的一个。 字典序的比较规则如下:长度均为 $2 n$ 的字符串 $s_{1 \sim 2 n}$ 比 $t_{1 \sim 2 n}$ 字典序小,当且仅当存在下标 $1 \le k \le 2 n$ 使得对于每个 $1 \le i < k$ 有 $s_i = t_i$ 且 $s_k < t_k$。
输入输出样例
输入样例 #1
2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
输出样例 #1
LRRLLRRRRL
-1
输入样例 #2
见附件中的 palin/palin2.in
输出样例 #2
见附件中的 palin/palin2.ans