[CSP-S 2021] 回文

GitHub 跳转原题关系图返回列表

固定首个取数方向后按匹配位置切成两段，用两端配对贪心构造操作串。

OJ: luogu

题目 ID: P7915

难度:提高+/省选-

标签:构造贪心双指针搜索

日期: 2026-07-06 08:46

题意

给定长度为 2n 的序列，其中 1..n 每个数都恰好出现两次。每次可以从当前序列左端或右端取出一个数，依次放到新序列 b 的末尾。

要求构造一个操作串，使最终得到的 b 是回文；如果有多种方案，输出字典序最小的操作串。规定 L < R。

思路

小数据可以直接按字典序枚举所有操作串，找到第一个能得到回文的方案：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72// brute.cpp：小数据暴力解，按字典序 DFS 枚举 L/R 操作直到得到回文。
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> origin;
string answer;
bool found;

bool is_palindrome(const vector<int> &b) {
    for (int i = 0, j = (int)b.size() - 1; i < j; i++, j--) {
        if (b[i] != b[j]) {
            return false;
        }
    }
    return true;
}

void dfs(int l, int r, vector<int> &b, string &ops) {
    if (found) {
        return;
    }
    if (l > r) {
        if (is_palindrome(b)) {
            answer = ops;
            found = true;
        }
        return;
    }

    // 字典序要求优先尝试 L。
    b.push_back(origin[l]);
    ops.push_back('L');
    dfs(l + 1, r, b, ops);
    ops.pop_back();
    b.pop_back();

    b.push_back(origin[r]);
    ops.push_back('R');
    dfs(l, r - 1, b, ops);
    ops.pop_back();
    b.pop_back();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        origin.assign(2 * n + 1, 0);
        for (int i = 1; i <= 2 * n; i++) {
            cin >> origin[i];
        }

        answer.clear();
        found = false;
        vector<int> b;
        string ops;
        dfs(1, 2 * n, b, ops);

        if (found) {
            cout << answer << '\n';
        } else {
            cout << -1 << '\n';
        }
    }

    return 0;
}

暴力的瓶颈是操作串有 2^(2n) 种。正解需要利用“每个数恰好出现两次”的性质。

一个回文序列的第一个数和最后一个数必须相同。因此，第一步只有两种本质尝试：

先取左端 a[1]，那么它的另一次出现必须作为最后一步被取走；
先取右端 a[2n]，那么它的另一次出现必须作为最后一步被取走。

因为 L 的字典序小于 R，我们先尝试第一种。如果能构造成功，它一定优于任何以 R 开头的方案。

以先取左端为例。设 a[1] 的另一次出现位置为 p。位置 p 的数要留到最后，剩下的元素被切成两段：

text

1[2, p-1]      [p+1, 2n]

后续每次要为回文的前半部分取一个数，同时为回文的后半部分预定一个相同的数。当前可取的前端只可能是左段左端或右段右端；对应的后端只可能是左段右端或右段左端。

所以每一步最多检查四种配对：

text

1
2
3
4左段左端  <-> 左段右端
左段左端  <-> 右段左端
右段右端  <-> 左段右端
右段右端  <-> 右段左端

为了字典序最小，能让当前操作为 L 时优先选 L，否则再选 R。每次记录前半部分操作，同时把匹配操作记录到后半部分；最后后半部分要反向拼回去。

如果先取左端失败，再用同样方法尝试先取右端。两次都失败才输出 -1。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137// main.cpp：固定第一个选择后，把剩余序列分成两段，贪心构造字典序最小方案。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int n;
int a[MAXN];
int first_pos[MAXN], second_pos[MAXN];

bool same_pos_invalid(int x, int y) {
    return x == y;
}

bool build_answer(bool choose_left_first, string &answer) {
    int total = 2 * n;
    int first_value;
    int match_pos;
    char first_op, last_op;
    int l1, r1, l2, r2;

    if (choose_left_first) {
        first_value = a[1];
        match_pos = (first_pos[first_value] == 1) ? second_pos[first_value] : first_pos[first_value];
        first_op = 'L';
        last_op = 'L';
        l1 = 2;
        r1 = match_pos - 1;
        l2 = match_pos + 1;
        r2 = total;
    } else {
        first_value = a[total];
        match_pos = (first_pos[first_value] == total) ? second_pos[first_value] : first_pos[first_value];
        first_op = 'R';
        // 最后只剩一个元素时，L/R 都能取走；为了字典序取 L。
        last_op = 'L';
        l1 = 1;
        r1 = match_pos - 1;
        l2 = match_pos + 1;
        r2 = total - 1;
    }

    string left_ops, right_ops;
    left_ops.push_back(first_op);

    for (int step = 1; step <= n - 1; step++) {
        bool done = false;

        if (l1 <= r1) {
            if (l1 < r1 && a[l1] == a[r1]) {
                left_ops.push_back('L');
                right_ops.push_back('L');
                l1++;
                r1--;
                done = true;
            } else if (l2 <= r2 && a[l1] == a[l2]) {
                left_ops.push_back('L');
                right_ops.push_back('R');
                l1++;
                l2++;
                done = true;
            }
        }

        if (!done && l2 <= r2) {
            if (l1 <= r1 && a[r2] == a[r1]) {
                left_ops.push_back('R');
                right_ops.push_back('L');
                r2--;
                r1--;
                done = true;
            } else if (l2 < r2 && a[r2] == a[l2]) {
                left_ops.push_back('R');
                right_ops.push_back('R');
                r2--;
                l2++;
                done = true;
            }
        }

        if (!done) {
            return false;
        }
    }

    if (l1 <= r1 || l2 <= r2) {
        return false;
    }

    answer = left_ops;
    for (int i = (int)right_ops.size() - 1; i >= 0; i--) {
        answer.push_back(right_ops[i]);
    }
    answer.push_back(last_op);
    return true;
}

void solve_one() {
    cin >> n;
    int total = 2 * n;
    for (int i = 1; i <= n; i++) {
        first_pos[i] = second_pos[i] = 0;
    }

    for (int i = 1; i <= total; i++) {
        cin >> a[i];
        if (first_pos[a[i]] == 0) {
            first_pos[a[i]] = i;
        } else {
            second_pos[a[i]] = i;
        }
    }

    string answer;
    if (build_answer(true, answer)) {
        cout << answer << '\n';
        return;
    }
    if (build_answer(false, answer)) {
        cout << answer << '\n';
        return;
    }
    cout << -1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    return 0;
}

复杂度

每组数据只会在线性指针上移动，每个位置最多被处理一次。

时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

总结

本题不要直接搜索完整操作串。先固定第一个数，就能确定最后一个数的位置；这个位置把剩余序列切成两段，后面的构造就变成“两段两端配对”。

字典序最小的核心是：先尝试首字母为 L 的方案，构造过程中也尽量让前半部分当前操作为 L。

P7915 [CSP-S 2021] 回文

题目描述

给定正整数 $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

输入 #1

text

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

输出 #1

text

1
2LRRLLRRRRL
-1

输入输出样例 #2

输入 #2

text

1见附件中的 palin/palin2.in

输出 #2

text

1见附件中的 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下面。

[CSP-S 2021] 回文

目录

题意

思路

代码

复杂度

总结