TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8754
  • 题目
  • P8754[CSP-S 2021] 回文
    限制 : 时间限制 : - MS   空间限制 : 524288 KB
    评测说明 : 1s,512MB
    问题描述

    给定正整数 \(n\) 和整数序列 \(a_1, a_2, \ldots, a_{2 n}\) ,在这 \(2 n\) 个数中, \(1, 2, \ldots, n\) 分别各出现恰好 \(2\) 次。现在进行 \(2 n\) 次操作,目标是创建一个长度同样为 \(2 n\) 的序列 \(b_1, b_2, \ldots, b_{2 n}\) ,初始时 \(b\) 为空序列,每次可以进行以下两种操作之一:

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

    我们的目的是让 \(b\) 成为一个回文数列,即令其满足对所有 \(1 \le i \le n\) ,有 \(b_i = b_{2 n + 1 - i}\) 。请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在【输出格式】中说明。

    输入格式

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

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

    第一行,包含一个正整数 \(n\) 。 第二行,包含 \(2 n\) 个用空格隔开的整数 \(a_1, a_2, \ldots, a_{2 n}\)

    输出格式

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

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

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

    字典序的比较规则如下:长度均为 \(2 n\) 的字符串 \(s_{1 \dots 2 n}\)\(t_{1 \dots 2 n}\) 字典序小,当且仅当存在下标 \(1 \le k \le 2 n\) 使得对于每个 \(1 \le i < k\)\(s_i = t_i\)\(s_k < t_k\)

    样例输入

    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]\) ,可以看出这是一个回文数列。

    另一种可能的操作方案是 \(\texttt{LRRLLRRRRR}\) ,但比答案方案的字典序要大。

    数据范围

    \(\sum n\) 表示所有 \(T\) 组测试数据中 \(n\) 的和。

    对所有测试点保证 \(1 \le T \le 100\)\(1 \le n\)\(\sum n \le 5 \times {10}^5\)

    测试点编号 \(T \le\) \(n \le\) \(\sum n \le\) 特殊性质
    \(1 \sim 7\) \(10\) \(10\) \(50\)
    \(8 \sim 10\) \(100\) \(20\) \(1000\)
    \(11 \sim 12\) \(100\) \(100\) \(1000\)
    \(13 \sim 15\) \(100\) \(1000\) \(25000\)
    \(16 \sim 17\) \(1\) \(5 \times {10}^5\) \(5 \times {10}^5\)
    \(18 \sim 20\) \(100\) \(5 \times {10}^5\) \(5 \times {10}^5\)
    \(21 \sim 25\) \(100\) \(5 \times {10}^5\) \(5 \times {10}^5\)

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