/ Vijos / 题库 /

回文

回文

时间限制:1秒  内存限制:256M


【问题描述】

  给定正整数 \(n\) 和整数序列 \(a_1, a_2, ..., a_{2n}\),在这 \(2n\) 个数中,\(1, 2, ... , n\) 分别各出现恰好 2 次。现在进行 \(2n\) 次操作,目标是创建一个长度同样为 \(2n\) 的序列 \(b_1, b_2, ..., b_{2n}\),初始时 \(b\) 为空序列,每次可以进行以下两种操作之一:
  1. 将序列 \(a\) 的开头元素加到 \(b\) 的末尾,并从 \(a\) 中移除
  2. 将序列 \(a\) 的末尾元素加到 \(b\) 的末尾,并从 \(a\) 中移除
  我们的目的是让 \(b\) 成为一个 回文数列. ,即令其满足对所有 \(1 ≤ i ≤ n\),有 \(b_i = b_{2n+1−i}\)。请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在【输出格式】中说明。

【输入格式】

  每个测试点包含多组测试数据。
  输入的第一行包含一个整数 \(T\),表示测试数据的组数。
  每组测试数据的第一行包含一个正整数 \(n\),第二行包含 \(2n\) 个用空格隔开的整数 \(a_1, a_2, ..., a_{2n}\)。

【输出格式】

  对每个测试数据输出一行答案。
  如果无法生成出回文数列,输出一行 ‐1,否则输出一行一个长度为 \(2n\) 的、由字符 L 或 R 构成的字符串(不含空格),其中 L 表示移除开头元素的操作 1,R 表示操作 2。你需要输出所有方案对应的字符串中字典序最小的一个。
  字典序的比较规则如下:长度均为 \(2n\) 的字符串 \(s_{1..2n}\) 比 \(t_{1..2n}\) 字典序小,当且仅当存在下标 \(1 ≤ k ≤ 2n\) 使得 \(∀1 ≤ i < k\) 有 \(s_i = t_i\) 且 \(s_k < t_k\)。

【输入输出样例1】

 Input

2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1

 Output

LRRLLRRRRL
‐1

【样例1解释】

  在第一组数据中,生成的的 b 数列是 4 5 3 1 2 2 1 3 5 4,可以看出这是一个回文数列。
  另一种可能的操作方案是 LRRLLRRRRR,但比答案方案的字典序要大。

【数据说明】

说明

【来源】

  Mr.he

信息

ID
2410
难度
(无)
分类
数据结构 | 队列贪心 点击显示
标签
递交数
0
已通过
0
通过率
?
被复制
1
上传者