P11352 「CSP-S 2021」回文
给定正整数 和整数序列 ,在这 个数中,分别各出现恰好次。现在进行 次操作,目标是创建一个长度同样为的序列 ,初始时为空序列,每次可以进行以下两种操作之一:
- 将序列 的开头元素加到的末尾,并从中移除。
- 将序列的末尾元素加到的末尾,并从中移除。
我们的目的是让成为一个回文数列,即令其满足对所有,有。请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在输出格式中说明。
每个测试点包含多组测试数据。
输入的第一行,包含一个整数,表示测试数据的组数。对于每组测试数据:
第一行,包含一个正整数。
第二行,包含个用空格隔开的整数。
对每组测试数据输出一行答案。
如果无法生成出回文数列,输出一行 ‐1
,否则输出一行一个长度为的、由字符 L
或 R
构成的字符串(不含空格),其中 L
表示移除开头元素的操作 1,R
表示操作 2。
你需要输出所有方案对应的字符串中字典序最小的一个。
字典序的比较规则如下:长度均为的字符串比字典序小,当且仅当存在下标 使得对于每个 有且 。
样例1说明
在第一组数据中,生成的数列是$[4,5,3,1,2,2,1,3,5,4],可以看出这是一个回文数列。
另一种可能的操作方案是 LRRLLRRRRR
,但比答案方案的字典序要大。
数据范围与提示
令 表示所有组测试数据中的和。
对所有测试点保证 ,。
测试点编号 | 特殊性质 | |||
---|---|---|---|---|
1~7 | 10 | 10 | 50 | 无 |
8~10 | 100 | 20 | 1000 | 无 |
11~12 | 100 | 100 | 1000 | 无 |
13~15 | 100 | 1000 | 25000 | 无 |
16~17 | 1 | 无 | ||
18~20 | 100 | 有 | ||
21~25 | 100 | 无 |
特殊性质:如果我们每次删除中两个相邻且相等的数,存在一种方式将序列删空(例如)。