A13521. Most socially-distanced subsequence
编程题
普及/提高-
知识点
题目描述
Given a permutation $p$ of length $n$ , find its subsequence $s_1$ , $s_2$ , $\ldots$ , $s_k$ of length at least $2$ such that:
- $|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$ is as big as possible over all subsequences of $p$ with length at least $2$ .
- Among all such subsequences, choose the one whose length, $k$ , is as small as possible.
If multiple subsequences satisfy these conditions, you are allowed to find any of them.
A sequence $a$ is a subsequence of an array $b$ if $a$ can be obtained from $b$ by deleting some (possibly, zero or all) elements.
A permutation of length $n$ is an array of length $n$ in which every element from $1$ to $n$ occurs exactly once.
- $|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$ is as big as possible over all subsequences of $p$ with length at least $2$ .
- Among all such subsequences, choose the one whose length, $k$ , is as small as possible.
If multiple subsequences satisfy these conditions, you are allowed to find any of them.
A sequence $a$ is a subsequence of an array $b$ if $a$ can be obtained from $b$ by deleting some (possibly, zero or all) elements.
A permutation of length $n$ is an array of length $n$ in which every element from $1$ to $n$ occurs exactly once.
输入格式
The first line contains an integer $t$ ( $1 \le t \le 2 \cdot 10^4$ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer $n$ ( $2 \le n \le 10^5$ ) — the length of the permutation $p$ .
The second line of each test case contains $n$ integers $p_1$ , $p_2$ , $\ldots$ , $p_{n}$ ( $1 \le p_i \le n$ , $p_i$ are distinct) — the elements of the permutation $p$ .
The sum of $n$ across the test cases doesn't exceed $10^5$ .
The first line of each test case contains an integer $n$ ( $2 \le n \le 10^5$ ) — the length of the permutation $p$ .
The second line of each test case contains $n$ integers $p_1$ , $p_2$ , $\ldots$ , $p_{n}$ ( $1 \le p_i \le n$ , $p_i$ are distinct) — the elements of the permutation $p$ .
The sum of $n$ across the test cases doesn't exceed $10^5$ .
输出格式
For each test case, the first line should contain the length of the found subsequence, $k$ . The second line should contain $s_1$ , $s_2$ , $\ldots$ , $s_k$ — its elements.
If multiple subsequences satisfy these conditions, you are allowed to find any of them.
If multiple subsequences satisfy these conditions, you are allowed to find any of them.
输入输出样例
输入 #1
2 3 3 2 1 4 1 3 4 2
输出 #1
2 3 1 3 1 4 2
说明/提示
In the first test case, there are $4$ subsequences of length at least $2$ :
- $[3,2]$ which gives us $|3-2|=1$ .
- $[3,1]$ which gives us $|3-1|=2$ .
- $[2,1]$ which gives us $|2-1|=1$ .
- $[3,2,1]$ which gives us $|3-2|+|2-1|=2$ .
So the answer is either $[3,1]$ or $[3,2,1]$ . Since we want the subsequence to be as short as possible, the answer is $[3,1]$ .
- $[3,2]$ which gives us $|3-2|=1$ .
- $[3,1]$ which gives us $|3-1|=2$ .
- $[2,1]$ which gives us $|2-1|=1$ .
- $[3,2,1]$ which gives us $|3-2|+|2-1|=2$ .
So the answer is either $[3,1]$ or $[3,2,1]$ . Since we want the subsequence to be as short as possible, the answer is $[3,1]$ .