真题解析:P7915 [CSP-S 2021] 回文(贪心·双端队列·回文构造)

题目来源：洛谷 P7915 [CSP-S 2021] 回文

一、题意速览

给定一个长度为 2n 的整数序列，其中 1 到 n 的每个数恰好出现两次。

我们要进行 2n 次操作，目标是把序列整理成一个回文数列（第 i 个位置和倒数第 i 个位置上的数相同）。每次操作二选一：

• L：把当前序列最左边的数，取出来接到结果序列的末尾；
• R：把当前序列最右边的数，取出来接到结果序列的末尾。

如果无论如何都整理不成回文，就输出 -1；否则输出一个由 L / R 组成的、长度为 2n 的字符串，表示每一步取哪一端——在所有能拼成回文的方案里，取字典序最小的那一个。

题目有多组测试数据，所有测试数据中 n 的总和不超过 5×10⁵。

二、输入输出样例

样例输入 #1

254 1 2 4 5 3 1 2 3 533 2 1 2 1 3

样例输出 #1

LRRLLRRRRL-1

样例解释 #1：第一组取出的数列是 4 5 3 1 2 2 1 3 5 4，首尾对称，是一个回文。第二组无论怎么取都拼不出回文，输出 -1。

三、考察知识点

• 贪心策略：判断这道题该不该用贪心，并理解它为什么正确（核心难点）。
• 双端队列 / 四指针模型：用两个双端队列（或四个指针）维护"被拆开的两段剩余元素"。
• 回文由外向内分层构造：回文不是从左到右拼的，而是一层一层从最外层往最内层配对。
• 字典序最小的处理：在每一步都优先尝试 L，保证整条操作串字典序最小。

四、核心思路：回文是"由外向内"建出来的

回文有一个重要性质：它最外层两个数相等，第二层两个数相等……也就是

b[1] = b[2n]b[2] = b[2n-1]b[3] = b[2n-2]...

所以回文是一层一层从外往里配对的：第 1 步和第 2n 步取到的数必须相等，第 2 步和第 2n-1 步取到的数必须相等……

这带来一个关键推论：第一步只能取 L 或 R。

• 如果第一步取 L，那取到的就是 a[1]，记这个值为 val；
• val 在序列里还有另一个副本，设它在位置 p2；
• 因为回文最外层两端相等，b[2n] 也得是 val，所以最后一步（第 2n 步）取的一定是 a[p2]。

把 a[1] 和 a[p2] 这两端固定后，剩下的元素被 a[p2] 自然分成了左右两段：

• 左段：夹在 a[1] 和 a[p2] 之间的数；
• 右段：a[p2] 另一边的数。

这两段各自就像一个双端队列：左段从靠近 a[1] 的那头取是 L，从靠近 a[p2] 的那头取也是 L；右段同理，不管从哪头取都是 R。

第一步取 R 的情况完全对称。

五、四种匹配条件

固定第一步后，我们从外往里一层层配对。第 step 层（对应回文第 step 和 2n-step+1 个位置）需要找两个相等的数，而且它们必须来自当前能取到的四个端点：左段的外端、左段的内端、右段的内端、右段的外端。

把它们记作 a[l1]、a[r1]、a[l2]、a[r2]，能成立的配对只有四种：

• 条件 1：a[l1] == a[r1]（左段两端相等）→ 两层都从左边取，记 L L；
• 条件 2：a[l1] == a[l2]（左段外端 = 右段内端）→ 先 L 后 R，记 L R；
• 条件 3：a[r1] == a[r2]（左段内端 = 右段外端）→ 先 R 后 L，记 R L；
• 条件 4：a[l2] == a[r2]（右段两端相等）→ 两层都从右边取，记 R R。

为什么只有这四种？因为每次必须刚好消耗两个值，而且它们都得在"当前可操作的位置"上。其余组合要么两个都是外层（取了之后内层还没暴露）、要么两个都是内层（取之前外层还挡着），都会破坏回文结构，不合法。

字典序怎么保证最小？L 的字典序比 R 小，所以：

1. 第一步优先试 L；
2. 四种条件里，能产出 L 的（条件 1、2）排在能产出 R 的（条件 3、4）前面；
3. 同一层里，把 L 分配给较早的 step 位置。

按这个优先级贪心，得到的操作串就是字典序最小的。可以证明：只要存在合法回文，这个按字典序优先的贪心一定能找到一种（嵌套回文结构的归纳可证）。

六、回溯与无解判定

并不是每选一个第一步都能走通。如果在某一层，四种条件一个都不满足，说明当前这个第一步走不通，需要回退去试另一种第一步：

• 先试第一步取 L（tryFirst(true)）；
• 不行再试第一步取 R（tryFirst(false)）；
• 两种都不行，才输出 -1。

注意：第一步取 L 和取 R 是把整条操作串完全分开考虑的，互不影响，所以直接两次 tryFirst 即可，不用复杂的回溯栈。

七、复杂度分析

• 每组数据里，找 val 的另一个副本需要 O(n)；
• 主循环从 step=2 到 n，每一步只做常数次比较和指针移动，O(n)；
• 总复杂度 O(T·n)，在 Σn ≤ 5×10⁵ 时非常轻松。

两个实现细节：

1. 用四个指针代替真的双端队列：直接在原始数组上移动 l1, r1, l2, r2 四个下标即可，不需要复制数组，常数更小。
2. 输入输出优化：n 到 5×10⁵ 时输入量很大，关掉同步 ios::sync_with_stdio(false); cin.tie(nullptr); 是必要的，否则可能超时。

八、参考代码

#include <bits/stdc++.h>using namespace std;const int MAXN = 1000005;int T, n;int a[2 * MAXN];char ans[2 * MAXN];const char L = 'L', R = 'R';   // 方向标记：取左端 / 取右端// 尝试以 firstL 作为第一步（true 取最左 L，false 取最右 R）// 若可行，把操作串写入 ans[1..2n] 并返回 truebool tryFirst(bool firstL){    int p1 = firstL ? 1 : 2 * n;   // 第一步取值的位置    int val = a[p1];    // 找到 val 的另一个副本位置 p2    int p2;    if (firstL) {        for (p2 = 2; p2 <= 2 * n; p2++)            if (a[p2] == val) break;    } else {        for (p2 = 2 * n - 1; p2 >= 1; p2--)            if (a[p2] == val) break;    }    // 剩余元素被 a[p2] 分成左右两段，各用一对指针维护（模拟双端队列）    int l1, r1, l2, r2;    if (firstL) {          // 左段：a[2..p2-1]，右段：a[p2+1..2n]        l1 = 2, r1 = p2 - 1;        l2 = p2 + 1, r2 = 2 * n;    } else {               // 左段：a[1..p2-1]，右段：a[p2+1..2n-1]        l1 = 1, r1 = p2 - 1;        l2 = p2 + 1, r2 = 2 * n - 1;    }    // 回文最外层由第一步的取值构成    ans[1] = firstL ? L : R;    ans[2 * n] = firstL ? L : R;    // 由外向内逐层配对：第 step 层与第 2n-step+1 层对称    for (int step = 2; step <= n; step++) {        // 条件1：左段两端相等 -> 两层都从左边取        if (l1 < r1 && a[l1] == a[r1]) {            ans[step] = L;            ans[2 * n + 1 - step] = L;            l1++; r1--;            continue;        }        // 条件2：左段外端 = 右段内端 -> 先 L 后 R（字典序更小，优先）        if (l1 <= r1 && l2 <= r2 && a[l1] == a[l2]) {            ans[step] = L;            ans[2 * n + 1 - step] = R;            l1++; l2++;            continue;        }        // 条件3：左段内端 = 右段外端 -> 先 R 后 L        if (l1 <= r1 && l2 <= r2 && a[r1] == a[r2]) {            ans[step] = R;            ans[2 * n + 1 - step] = L;            r1--; r2--;            continue;        }        // 条件4：右段两端相等 -> 两层都从右边取        if (l2 < r2 && a[l2] == a[r2]) {            ans[step] = R;            ans[2 * n + 1 - step] = R;            l2++; r2--;            continue;        }        // 四种条件都不满足，当前第一步不可行        return false;    }    return true;}int main(){    ios::sync_with_stdio(false);    cin.tie(nullptr);    cin >> T;    while (T--) {        cin >> n;        for (int i = 1; i <= 2 * n; i++)            cin >> a[i];        // 优先尝试第一步取 L（L 字典序更小）        if (tryFirst(true)) {            ans[2 * n + 1] = '\0';            cout << (ans + 1) << '\n';        } else if (tryFirst(false)) {            ans[2 * n + 1] = '\0';            cout << (ans + 1) << '\n';        } else {            cout << "-1\n";        }    }    return 0;}