思路与算法

先尝试首步L，失败再尝试R。首个数的另一次出现必须是回文最后一项，暂时固定该位置。剩余数组被它分为左右两段，分别用双端指针表示。同步构造回文前后两端：前半步只能从两段外端取，配对的后半步只能从两段内端取；比较四种端点配对，优先选择前半步为L的合法项，写入对称操作。最后一个元素只有一种取值，操作选L。

正确性说明

每个数只出现两次，因此指定前半步后，其配对位置唯一；只有该位置已经处在某段内端，才可能成为对应的倒序后半步。端点相等时移除这一对保持两段不变式。若左右外端相等而无法与内端配对，它们都应在此前固定最后元素之前被取走，不能互作最终配对，所以不是一个被遗漏的选择。对同一前半步无两个不同配对位置；若L、R均合法，先完成L配对可与可行方案的对称取对次序交换，不影响各段端点顺序，字典序更优。归纳得到每个首步下的最小方案；L首步优先给全局最小，两者都失败才无解。

复杂度

每组O(n)时间、O(n)空间，含双端区间、答案字符串初始化；至多两次尝试，总O(∑n)。

易错点

字典序要求真实L<R；最终单元素取L。不能只输出任意回文操作；-1使用半角负号。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

string solve(const vector<int> &a, bool right) {
    int N = a.size(), n = N / 2, start = right ? N - 1 : 0, p = -1;
    for (int i = 0; i < N; i++)
        if (i != start && a[i] == a[start])
            p = i;
    int l = right ? 0 : 1, r = p - 1, L = p + 1, R = right ? N - 2 : N - 1;
    string ans(N, 'L');
    ans[0] = right ? 'R' : 'L';
    for (int i = 1; i < n; i++) {
        if (l < r && a[l] == a[r]) {
            ans[i] = 'L';
            ans[N - 1 - i] = 'L';
            l++;
            r--;
        } else if (l <= r && L <= R && a[l] == a[L]) {
            ans[i] = 'L';
            ans[N - 1 - i] = 'R';
            l++;
            L++;
        } else if (l <= r && L <= R && a[R] == a[r]) {
            ans[i] = 'R';
            ans[N - 1 - i] = 'L';
            R--;
            r--;
        } else if (L < R && a[R] == a[L]) {
            ans[i] = 'R';
            ans[N - 1 - i] = 'R';
            R--;
            L++;
        } else
            return "";
    }
    return ans;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(2 * n);
        for (int &x : a)
            cin >> x;
        string ans = solve(a, false);
        if (ans.empty())
            ans = solve(a, true);
        cout << (ans.empty() ? "-1" : ans) << "\n";
    }
}