#2134231351. [CSP-S 2021] 回文

内存限制:512 MiB 时间限制:1000 ms 输入文件:palin.in 输出文件:palin.out
题目类型:传统 评测方式:文本比较
上传者: j27eGU

题目描述

一. 题目概况

中文题目名称 回文
英文题目与子目录名
可执行文件名
输入文件名
输出文件名
每个测试点时限
测试点数目
测试点分值
附加样例文件
结果比较方式 全文比较(过滤行末空格)
题目类型 传统
运行内存上限

二. 提交源程序文件名

对于C++语言
对于C语言
对于pascal语言

3. 回文

()

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

  1. 将序列 的开头元素加到 的末尾,并从 中移除。
  2. 将序列 的末尾元素加到 的末尾,并从 中移除。

我们的目的是让 成为一个回文数列,即令其满足对所有 ,有 。请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在【输出格式】中说明。

输入格式

每个测试点包含多组测试数据。

输入的第一行,包含一个整数 ,表示测试数据的组数。对于每组测试数据:

第一行,包含一个正整数
第二行,包含 个用空格隔开的整数

输出格式

对每组测试数据输出一行答案。

如果无法生成出回文数列,输出一行 -1,否则输出一行一个长度为 的、由字符 LR 构成的字符串(不含空格),其中 L 表示移除开头元素的操作 1,R 表示操作 2。

你需要输出所有方案对应的字符串中字典序最小的一个。

字典序的比较规则如下:长度均为 的字符串 字典序小,当且仅当存在下标 使得对于每个

样例

样例 #1

样例输入 #1

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

样例输出 #1

LRRLLRRRRL
-1

样例 #2

样例输入 #2

见附件中的 palin/palin2.in

样例输出 #2

见附件中的 palin/palin2.ans

数据范围与提示

【样例解释 #1】

在第一组数据中,生成的的 数列是 ,可以看出这是一个回文数列。

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

【数据范围】

表示所有 组测试数据中 的和。

对所有测试点保证

测试点编号 特殊性质

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

原题链接:https://www.luogu.com.cn/problem/P7915