回文

对一个包含 $2n$ 个整数（数字 $1 \sim n$ 各出现两次）的序列 $a$ 进行 $2n$ 次弹出操作：每次只能从序列 $a$ 的开头（记为 L）或末尾（记为 R）取出一个数依次加入新序列 $b$，使得最终生成的序列 $b$ 构成回文串。如果存在多种可行的操作方案，需输出字典序最小的操作序列（即包含字符 L 和 R 的字符串）；若无法构成回文串则输出 -1。

October 23, 2021CSP-S1分钟阅读

半圆形拱顶拜占庭风格马赛克镶嵌画，中心是水盆，两侧对称站立两只孔雀，拱弧上刻有希腊语回文铭文 ΝΙΨΟΝ ΑΝΟΜΗΜΑΤΑ ΜΗ ΜΟΝΑΝ ΟΨΙΝ。

题目描述

给定正整数 $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$ 为空序列，每次可以进行以下两种操作之一：

将序列 $a$ 的开头元素加到 $b$ 的末尾，并从 $a$ 中移除。
将序列 $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$ 使得对于每个 $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

样例解释

在第一组数据中，生成的的 $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]$ ）。

本题中“字典序最小的操作方案”指的是：由 $2n$ 个操作字符（'L' 与 'R'）拼成的字符串字典序最小。

由于字符的 ASCII 码关系为 'L' $<$ 'R'，比较两个方案时，从第 1 个操作字符开始逐位对比：

在第一个不相同的操作位置上，字符为 'L' 的方案字典序更小（优先级更高）。
示例："LLRLL" 的字典序小于 "LRLLL"（在第 2 位上 'L' $<$ 'R'）。

$b_1$ 决定了 $b_{2n}$ （二者必须相等）。为了优先保证字典序最小，先尝试第一步选 L（取 $a[1]$ ），找到与 $a[1]$ 相等的位置 $p$ ；若无解，再尝试第一步选 R（取 $a[2n]$ ）。

假设第一步选了 $a[1]$ ，以 $a[1]$ 的匹配位置 $p$ 为分界点，将剩下的元素划分为两个独立的双端队列：

左区间： $[2, p-1]$ （左端点 $L_1$ ，右端点 $R_1$ ）
右区间： $[p+1, 2n]$ （左端点 $L_2$ ，右端点 $R_2$ ）

每次从外侧端点（ $L_1$ 或 $R_2$ ）挑选一个数，匹配内侧端点（ $R_1$ 或 $L_2$ ）的数。按以下优先级依次尝试：

取 $a[L_1]$ 匹配 $a[R_1]$ （左区间内部匹配） $\rightarrow$ 前半加 L，后半加 L
取 $a[L_1]$ 匹配 $a[L_2]$ （左区间左端匹配右区间左端） $\rightarrow$ 前半加 L，后半加 R
取 $a[R_2]$ 匹配 $a[R_1]$ （右区间右端匹配左区间右端） $\rightarrow$ 前半加 R，后半加 L
取 $a[R_2]$ 匹配 $a[L_2]$ （右区间内部匹配） $\rightarrow$ 前半加 R，后半加 R

若这四种匹配均无法满足，说明当前初始选择无解。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int n;
vector<int> a;

// 模拟 n-1 步双端队列匹配
bool solve(int l1, int r1, int l2, int r2, string &ans_left, string &ans_right) {
    for (int step = 1; step < n; ++step) {
        // 1. 优先尝试从左区间的左端 l1 开始匹配 (对应前半段 + 'L')
        if (l1 <= r1 && l1 < r1 && a[l1] == a[r1]) { // 匹配左区间右端 r1
            l1++;
            r1--;
            ans_left += 'L';
            ans_right += 'L';
        } else if (l1 <= r1 && l2 <= r2 && a[l1] == a[l2]) { // 匹配右区间左端 l2
            l1++;
            l2++;
            ans_left += 'L';
            ans_right += 'R';
        }
        // 2. 再尝试从右区间的右端 r2 开始匹配 (对应前半段 + 'R')
        else if (l2 <= r2 && l1 <= r1 && a[r2] == a[r1]) { // 匹配左区间右端 r1
            r2--;
            r1--;
            ans_left += 'R';
            ans_right += 'L';
        } else if (l2 <= r2 && l2 < r2 && a[r2] == a[l2]) { // 匹配右区间左端 l2
            r2--;
            l2++;
            ans_left += 'R';
            ans_right += 'R';
        } else {
            return false;
        }
    }
    return true;
}

void process() {
    cin >> n;
    a.resize(2 * n + 1);
    for (int i = 1; i <= 2 * n; ++i) {
        cin >> a[i];
    }

    // 情况一：第一步选 L（即取出 a[1]）
    int p1 = -1;
    for (int i = 2; i <= 2 * n; ++i) {
        if (a[i] == a[1]) {
            p1 = i;
            break;
        }
    }

    if (p1 != -1) {
        // ans_left 记录前半部分(第 1 ~ n 步)的操作，初始选 L (取 a[1])
        // ans_right 记录后半部分(第 n+1 ~ 2n 步)的操作
        // 这里的 "L" 代表最后一步(第 2n 步)取出 a[p1] 的操作：
        // 此时序列只剩唯一元素 a[p1]，左右端点等价，为满足字典序最小优先记为 'L'
        // (注：ans_right 在追加完后续操作后会整体 reverse，初始的 "L" 会翻转到最终字符串的末尾)
        string ans_left = "L", ans_right = "L";

        // 左区间 [2, p1-1]，右区间 [p1+1, 2*n]
        if (solve(2, p1 - 1, p1 + 1, 2 * n, ans_left, ans_right)) {
            // 将倒序收集的后半段（第 2n ~ n+1 步）翻转为正确的正序（第 n+1 ~ 2n 步）
            reverse(ans_right.begin(), ans_right.end());

            cout << ans_left << ans_right << "\n";
            return;
        }
    }

    // 情况二：第一步选 R（即取出 a[2*n]）
    int p2 = -1;
    for (int i = 1; i < 2 * n; ++i) {
        if (a[i] == a[2 * n]) {
            p2 = i;
            break;
        }
    }

    if (p2 != -1) {
        string ans_left = "R", ans_right = "L";
        // 左区间 [1, p2-1]，右区间 [p2+1, 2*n-1]
        if (solve(1, p2 - 1, p2 + 1, 2 * n - 1, ans_left, ans_right)) {
            reverse(ans_right.begin(), ans_right.end());
            cout << ans_left << ans_right << "\n";
            return;
        }
    }

    cout << -1 << "\n";
}

int main() {
    // 快速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        process();
    }

    return 0;
}

时间复杂度：每一组数据只需移动双指针匹配 n 次，故单组数据复杂度为 O(n)。处理全部测试点耗时大约在几十毫秒以内。
空间复杂度：存储数组 a 和答案串，空间复杂度为 O(n)。

思路分析

确定第一个元素

划分两个双端队列

贪心选择策略

参考代码

复杂度分析