#CSPS2021C. 回文(Palindrome)
回文(Palindrome)
题目描述
给定正整数 和整数序列 ,在这 个数中, 分别各出现恰好 次。现在进行 次操作,目标是创建一个长度同样为 的序列 ,初始时 为空序列,每次可以进行以下两种操作之一:
- 将序列 的开头元素加到 的末尾,并从 中移除
- 将序列 的末尾元素加到 的末尾,并从 中移除
我们的目的是让 成为一个 回文数列,即令其满足对所有 ,有 。 请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在【输出格式】中说明。
输入格式
从文件 palin.in
中读入数据。
每个测试点包含多组测试数据。
输入的第一行包含一个整数 ,表示测试数据的组数。
每组测试数据的第一行包含一个正整数 ,第二行包含 个用空格隔开的整数 。
输出格式
输出到文件 palin.out
中。
对每个测试数据输出一行答案。
如果无法生成出回文数列,输出一行 ,否则输出一行一个长度为 的、由字符 或 构成的字符串(不含空格),其中 表示移除开头元素的操作 , 表示操作 。
你需要输出所有方案对应的字符串中字典序最小的一个。
字典序的比较规则如下:长度均为 的字符串 比 $t_{1..2n} 字典序小,当且仅当存在下标 使得 有 且 。
2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
LRRLLRRRRL
‐1
样例 1 解释
在第一组数据中,生成的的 数列是 $4\space 5\space 3\space 1\space 2\space 2\space 1\space 3\space 5\space 4$,可以看出这是一个回文数列。 另一种可能的操作方案是 ,但比答案方案的字典序要大。
样例 2
见选手目录下的 palin2.in 与 palin2.ans。
数据范围与提示
令 表示所有 组测试数据中 的和。 对所有测试点保证 $1 \leq T \leq 100, 1 \leq n, \sum n \leq 5 \times 10^5$。
测试点编号 | 特殊性质 | |||
---|---|---|---|---|
无 | ||||
有 | ||||
无 |
特殊性质:如果我们每次删除 中两个相邻且相等的数,存在一种方式将序列删空(例如 )。