1093: 「CSP-S 2021」回文

内存限制:1024 MB 时间限制:5.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:0

题目描述

给定正整数 n 和整数序列 a1, a2, ... ,a2n,在这 2n 个数中,1,2,...,n 分别各出现恰好 2 次。现在进行 2n 次操作,目标是创建一个长度同样为 2n 的序列 b1, b2, . . . , b2n, 初始时 b 为空序列,每次可以进行以下两种操作之一:

  • 将序列 a 的开头元素加到 b 的末尾,并从 a 中移除
  • 将序列 a 的末尾元素加到 b 的末尾,并从 a 中移除

我们的目的是让 b 成为一个回文数列,即令其满足对所有 1 ≤ i ≤ n,有 bi = b2n+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 =t且 sk<tk

输入样例 复制

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

输出样例 复制

LRRLLRRRRL
‐1

数据范围与提示

【样例 1 解释

在第一组数据中,生成的的 b 数列是4 5 3 1 2 2 1 3 5 4,可以看出这是一个 回文数列。

另一种可能的操作方案是 LRRLLRRRRR,但比答案方案的字典序要大。 

样例 2】

见选手目录下的 palin/palin2.in 与 palin/palin2.ans。 

【数据范围】

令 ∑ 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
13∼15 1000 25000
16∼17 1 5×105 5×105
18∼20 100
21∼25

特殊性质:  如果我们每次删除 a 中两个相邻且相等的数,存在一种方式将序列删空 (例如a = [1,2,2,1])。

【附件下载】

    plain