CSP2021 -T3

$$Hello!\\World$$

$Hello$

题解

## 题目描述

给定正整数 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 的、由字符 LR 构成的字符串(不含空格),其中 L 表示移除开头元素的操作 1,R 表示操作 2。

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

    字典序的比较规则如下:长度均为 2 n 的字符串 s_{1 \sim 2 n}t_{1 \sim 2 n} 字典序小,当且仅当存在下标 1 \le k \le 2 n 使得对于每个 1 \le is_i = t_is_k

    样例 #1

    样例输入 #1

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

    样例输出 #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 1001 \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])。

做法

先看性质在贪心

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1000000;
#define doit(a,s,q0,q1)ans.push_back(a),sna.push_back(s),q0.pop_front(),q1.pop_back()
#define sf(q) q.size() ? q.front() : 0
#define sb(q) q.size() ? q.back() : 0
int a[N], b[N], c[N], n;
bool check(char cc) {
    deque<int> q[2];
    string ans, sna;
    ans.push_back(cc);
    sna.push_back('L');
    if (cc == 'L') {
        for (int i = 2; i < c[1]; i++) q[0].push_back(i);
        for (int i = n; i > c[1]; i--) q[1].push_back(i);
    }
    else {
        for (int i = 1; i < c[n]; ++i) q[0].push_back(i);
        for (int i = n - 1; i > c[n]; --i) q[1].push_back(i);
    }
    while (q[0].size() > 0 || q[1].size() > 0)
        if (int x[] = { sf(q[0]),sf(q[1])},
            y[] = { sb(q[0]),sb(q[1])}; c[x[0]] == y[0])
            doit('L', 'L', q[0], q[0]);
        else if (c[x[0]] == y[1])
            doit('L', 'R', q[0], q[1]);
        else if (c[x[1]] == y[0])
            doit('R', 'L', q[1], q[0]);
        else if (c[x[1]] == y[1])
            doit('R', 'R', q[1], q[1]);
        else return false;
    reverse(sna.begin(), sna.end());
    ans += sna;
    cout << ans << endl;
    return true;
}
int main() {
    int _;
    scanf("%d", &_);
    while (_--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) b[i] = 0;
        n *= 2;
        c[0] = -1;
        for (int i = 1; i <= n; ++i)
            if (scanf("%d", &a[i]);b[a[i]])
                c[c[b[a[i]]] = i] = b[a[i]];
            else
                b[a[i]] = i;
        if (!check('L') && !check('R')) puts("-1");
    }
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇