s02271. CSP-S 2021 复赛 T3 回文 未做

时间限制：1s　内存限制：512MB　来源：洛谷 P7915

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

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

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

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

输入的第一行，包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

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

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

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

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

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

【样例解释 #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$。

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

【hack 数据提供】
@潜在了H2O下面。