P7915 回文

CSP 2021 T3

题面

题目描述

给定正整数 $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$ 使得对于每个 $1 \le i < k$ 有 $s_i = t_i$ 且 $s_k < t_k$。

样例 #1

样例输入 #1

2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3

样例输出 #1

LRRLLRRRRL
-1

样例 #2

样例输入 #2

见附件中的 palin/palin2.in

样例输出 #2

见附件中的 palin/palin2.ans

提示

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

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

思路

假设先选左边，那么我们找到序列中和最左边这个数相同的数的位置 $x$，那么就分为了 $1\sim{x-1}$ 和 $x\sim{len}$ 这两端区间，$x$ 一定是最后弹出的。

我们分别维护两个双端队列：$1\to{x-1}$ 和 $len\to{x}$，设为 $a$ 和 $b$

那么我们就要找是否有某对 队头和队尾相等。

• 假如是 $a$ 的队头和队尾相同，那么一定对应着对称的两次 $L$
• 假如是 $b$ 的队头和队尾相同，那么一定对应着两次对称的 $R$
• 假如是 $a$ 的队头和 $b$ 的队尾相同，那么假如弹出 $a$ 队头是第 $i$ 个数，那么弹出 $b$ 队尾就是倒数第 $i$ 个数。
• 假如 $b$ 的队头和 $a$ 的队尾相同，那么假如弹出 $b$ 队头是第 $i$ 个数，那么弹出 $a$ 队尾就是倒数第 $i$ 个数。
• 假如都不符合，那么就找不到一种合法的情况。

先选右边也是同理。

分别维护两个字符串，表示从队头出还是从队尾出，注意队尾出的操作是倒序，要进行一次翻转。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;

int a[N];
int n;

// struct Mydeque
// {
//     int l, r;
//     int z[N << 1];
//     Mydeque()
//     {
//         memset(z, 0, sizeof(z));
//         l = r = N;
//     }
//     int back()
//     {
//         return z[r];
//     }
//     int front()
//     {
//         return z[l + 1];
//     }
//     void push_back(int x)
//     {
//         z[++r] = x;
//     }
//     void push_front(int x)
//     {
//         z[l--] = x;
//     }
//     void pop_back()
//     {
//         if(!empty()) r--;
//     }
//     void pop_front()
//     {
//         if(!empty()) l++;
//     }
//     void clear()
//     {
//         memset(z, 0, sizeof(z));
//         l = r = N;
//     }
//     bool empty()
//     {
//         return r == l;
//     }
//     int size()
//     {
//         return r - l;
//     }
// }q1, q2;

inline int read()
{
    int x = 0, y = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-') y = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar();
    }
    return x * y;
}

string solve()
{
    string res, res1, res2;
    deque<int> q1;
    deque<int> q2;
    q1.push_back(a[1]);
    bool bj = false;
    for(int i = 2; i <= 2 * n; i++)
    {
        if(a[i] == a[1]) bj = true;
        if(!bj) q1.push_back(a[i]);
        else q2.push_front(a[i]);
    }
    bj = false;
    for(int i = 1; i <= n; i++)
    {
        int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
        if(!q1.empty())
        {
            a1 = q1.front();
            a2 = q1.back();
        }
        if(!q2.empty())
        {
            b1 = q2.front();
            b2 = q2.back();
        }
        if((int)q1.size() != 1 && a1 == a2 && a1)
        {
            res1 += 'L';
            res2 += 'L';
            q1.pop_front();
            q1.pop_back();
        }
        else if(a1 == b2 && a1)
        {
            res1 += 'L';
            res2 += 'R';
            q1.pop_front();
            q2.pop_back();
        }
        else if(a2 == b1 && a2)
        {
            res1 += 'R';
            res2 += 'L';
            q1.pop_back();
            q2.pop_front();
        }
        else if((int)q2.size() != 1 && b1 == b2 && b1)
        {
            res1 += 'R';
            res2 += 'R';
            q2.pop_front();
            q2.pop_back();
        }
        else
        {
            bj = true;
            break;
        }
    }
    if(!bj)
    {
        reverse(res2.begin(), res2.end());
        return res1 + res2;
    }
    res1.clear();
    res2.clear();
    q1.clear();
    q2.clear();
    q2.push_back(a[n * 2]);
    bj = false;
    for(int i = 2 * n - 1; i >= 1; i--)
    {
        if(a[i] == a[n * 2]) bj = true;
        if(!bj) q2.push_back(a[i]);
        else q1.push_front(a[i]);
    }
    for(int i = 1; i <= n; i++)
    {
        int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
        if(!q1.empty())
        {
            a1 = q1.front();
            a2 = q1.back();
        }
        if(!q2.empty())
        {
            b1 = q2.front();
            b2 = q2.back();
        }
        if((int)q1.size() != 1 && a1 == a2 && a1)
        {
            res1 += 'L';
            res2 += 'L';
            q1.pop_front();
            q1.pop_back();
        }
        else if(a1 == b2 && a1)
        {
            res1 += 'L';
            res2 += 'R';
            q1.pop_front();
            q2.pop_back();
        }
        else if(a2 == b1 && a2)
        {
            res1 += 'R';
            res2 += 'L';
            q1.pop_back();
            q2.pop_front();
        }
        else if((int)q2.size() != 1 && b1 == b2 && b1)
        {
            res1 += 'R';
            res2 += 'R';
            q2.pop_front();
            q2.pop_back();
        }
        else return "NO";
    }
    reverse(res2.begin(), res2.end());
    return res1 + res2;
}

int main()
{
    // freopen("E:\\下载\\P7915_17.in", "r", stdin);
    // freopen("E:\\下载\\P7915_17.ans", "w", stdout);
    int t;
    scanf("%d", &t);
    while(t--)
    {
        n = read();
        for(int i = 1; i <= 2 * n; i++)
        {
            a[i] = read();
        }
        string ans = solve();
        if(ans == "NO")
            puts("-1");
        else
        {
            ans[ans.size() - 1] = 'L';
            cout << ans << endl;
        }
    }
    return 0;
}