CF2001D.Longest Max Min Subsequence

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个整数序列 $a_1, a_2, \ldots, a_n$ 。设 $S$ 为所有可能的不含重复元素的非空子序列的集合。你的目标是找到 $S$ 中最长的序列。如果有多个这样的序列，要求在将奇数位置的元素乘以 $-1$ 后，字典序最小的那个。

例如，给定 $a = [3, 2, 3, 1]$ ， $S = \{[1], [2], [3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 3, 1], [3, 2, 1]\}$ 。那么 $[2, 3, 1]$ 和 $[3, 2, 1]$ 是最长的序列，而 $[3, 2, 1]$ 是答案，因为 $[-3, 2, -1]$ 的字典序比 $[-2, 3, -1]$ 小。

如果序列 $c$ 可以通过从序列 $d$ 中删除若干（可能为零或全部）元素得到，则称 $c$ 是 $d$ 的一个子序列。

如果满足以下任一条件，则称序列 $c$ 的字典序小于序列 $d$ ：

$c$ 是 $d$ 的前缀，且 $c \ne d$ ；
在 $c$ 和 $d$ 第一个不同的位置， $c$ 的元素小于 $d$ 对应位置的元素。

输入格式

每组测试数据包含多个测试用例。第一行包含一个整数 $t$ （ $1 \le t \le 5 \cdot 10^4$ ），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ （ $1 \le n \le 3 \cdot 10^5$ ），表示序列 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \le a_i \le n$ ），表示序列 $a$ 。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出答案，格式如下：

第一行输出一个整数 $m$ ，表示序列 $b$ 的长度。

第二行输出 $m$ 个整数 $b_1, b_2, \ldots, b_m$ ，表示序列 $b$ 。

输入输出样例

输入#1

4
4
3 2 1 3
4
1 1 1 1
9
3 2 1 3 2 1 3 2 1
1
1

输出#1

输入#2

10
2
1 2
10
5 2 1 7 9 7 2 5 5 2
2
1 2
10
2 2 8 7 7 9 8 1 9 6
9
9 1 7 5 8 5 6 4 1
3
3 3 3
6
1 6 4 4 6 5
6
3 4 4 5 3 3
10
4 1 4 5 4 5 10 1 5 1
7
1 2 1 3 2 4 6

输出#2

2
1 2
5
5 1 9 7 2
2
1 2
6
2 7 9 8 1 6
7
9 1 7 5 8 6 4
1
3
4
1 4 6 5
3
4 5 3
4
5 4 10 1
5
2 1 3 4 6

说明/提示

在第一个样例中， $S = \{[1], [2], [3], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 1, 3], [3, 2, 1]\}$ 。其中 $[2, 1, 3]$ 和 $[3, 2, 1]$ 是最长的序列， $[-3, 2, -1]$ 的字典序比 $[-2, 1, -3]$ 小，所以 $[3, 2, 1]$ 是答案。

在第二个样例中， $S = \{[1]\}$ ，所以 $[1]$ 是答案。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页