当前位置:首页 > 数学 > 构造 > 正文
洛谷P7915回文(CSPS2021)
170+

题目大意:一个长度为2n的整数序列,1~n分别出现两次,每次只能从两端取出元素放入队列,是否能构造出一个回文队列?如果可以输出操作字典序小的方案,否则输出-1。

题目描述

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

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

输出样例 #1

LRRLLRRRRL
-1

输入样例 #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]$)。

解题思路

模拟样例(m=5、n=10):
4 1 2 4 5 3 1 2 3 5
1 4 5 10 9 8 7 6 3 2 (放入新序列的时间)

最后m个数,始终是连在一起的,如果不连续,中间的数字怎么办呢?

我们可以在暴力基础上,用这个方法进行剪枝:

暴力的时候,第一个可以选择左端点,也可以选择右端点,优先选择左边,这样最后一个入队的数字也确定了。之后选择数字,需要保证他的另一个位置的数字,必须跟时间戳大于m的连在一起。

只要找到一组方案,就不需要再搜索下去,因为我们是安装字典序搜索的,这样能够通过洛谷的民间数据。

但还是可以卡,因为如果无解,前面既可以选择L,又可以选择R,会重复很多次。对于这种情况,我们可以发现,两边都可以选,只是顺序不同而已,最终是否有解是一样的,所以,只要搜过L,就不需要搜R,就保证了搜索是一条路走到底,不会超时。

程序实现

v数组记录入队时间,x[i]数组记录数字i第一次出现的位置,y[i]记录数字i第二次出现的位置。

About

坚决不Copy代码!

本文标签:,,,,,,,,,,

洛谷P7915回文(CSPS2021):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter