Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5608 --3.回文（palin）
5608: 3.回文（palin）
警告！
题目
状态
题解
题目描述
给定正整数 $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}$。
输出
对每组测试数据输出一行答案。 如果无法生成出回文数列，输出一行 `‐1`，否则输出一行一个长度为 $2 n$ 的、由字符 `L` 或 `R` 构成的字符串（不含空格），其中 `L` 表示移除开头元素的操作 1，`R` 表示操作 2。 你需要输出所有方案对应的字符串中字典序最小的一个。 字典序的比较规则如下：长度均为 $2 n$ 的字符串 $s_{1 \sim 2 n}$ 比 $t_{1 \sim 2 n}$ 字典序小，当且仅当 存在下标 $1 \le k \le 2 n$ 使得 $\forall 1 \le i < k$ 有 $s_i = t_i$ 且 $s_k < t_k$。
样例输入输出
输入#1
复制
2 5 4 1 2 4 5 3 1 2 3 5 3 3 2 1 2 1 3
输出#1
复制
LRRLLRRRRL ‐1
提示
**【样例解释 #1】** 在第一组数据中，生成的的 $b$ 数列是 $[4, 5, 3, 1, 2, 2, 1, 3, 5, 4]$，可以看出这是一个回文数列。 另一种可能的操作方案是 `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]$）。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
点击显示
递交数
7
已通过
2
通过率
29%
时间限制
1 秒
内存限制
512 MB
来源
2021CSP S2
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和