P13786 [eJOI 2022] LCS of Permutations

对于两个序列 $x$ 和 $y$，我们定义 $LCS(x, y)$ 为它们的最长公共子序列的长度。 现在给定 4 个整数 $n, a, b, c$。请判断是否存在 3 个 $1 \sim n$ 的排列 $p, q, r$，满足： - $LCS(p, q) = a$ - $LCS(p, r) = b$ - $LCS(q, r) = c$ 如果存在这样的排列，请输出任意一组满足条件的排列三元组。 一个排列 $p$ 是 $1 \sim n$ 的一个排列，当且仅当 $p$ 是长度为 $n$ 的序列，并且其中所有元素互不相同，且取值范围为 $[1, n]$。例如，$(2, 4, 3, 5, 1)$ 是 $1 \sim 5$ 的一个排列，而 $(1, 2, 1, 3, 5)$ 和 $(1, 2, 3, 4, 6)$ 则不是。 一个序列 $c$ 是序列 $d$ 的一个子序列，当且仅当 $c$ 可以通过从 $d$ 中删除若干（可能是零个，也可能是全部）元素得到。例如，$(1, 3, 5)$ 是 $(1, 2, 3, 4, 5)$ 的子序列，而 $(3, 1)$ 不是。 两个序列 $x$ 和 $y$ 的最长公共子序列，指的是一个同时为 $x$ 和 $y$ 的子序列的最长序列。例如，$x = (1, 3, 2, 4, 5)$ 与 $y = (5, 2, 3, 4, 1)$ 的最长公共子序列为 $z = (2, 4)$，因为它既是两者的子序列，又是所有公共子序列中最长的一个。此时 $LCS(x, y) = 2$。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例包含一行 5 个整数 $n, a, b, c, output$（$1 \leq a \leq b \leq c \leq n \leq 2 \cdot 10^5$, $0 \leq output \leq 1$）。 - 若 $output = 0$，仅需判断是否存在这样的排列。 - 若 $output = 1$，在存在的情况下，还需输出一组满足条件的排列三元组。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，若存在满足条件的排列 $p, q, r$，则第一行输出 "YES"，否则输出 "NO"。 如果 $output = 1$ 且存在解，则再输出三行： - 第一行输出排列 $p$：$p_1, p_2, \ldots, p_n$ - 第二行输出排列 $q$：$q_1, q_2, \ldots, q_n$ - 第三行输出排列 $r$：$r_1, r_2, \ldots, r_n$ 如果有多组解，输出任意一组即可。 输出时字母大小写不敏感（例如 "YES"、"Yes"、"yes"、"yEs" 都视为正确）。

### 样例解释 在第一个测试用例中，$LCS((1), (1)) = 1$。 在第二个测试用例中，可以证明不存在这样的排列。 在第三个测试用例中，其中一种可能的解为： - $p = (1, 3, 5, 2, 6, 4)$ - $q = (3, 1, 5, 2, 4, 6)$ - $r = (1, 3, 5, 2, 4, 6)$ 此时： - $LCS(p, q) = 4$（例如 $(1, 5, 2, 6)$ 是一个最长公共子序列） - $LCS(p, r) = 5$（例如 $(1, 3, 5, 2, 4)$） - $LCS(q, r) = 5$（例如 $(3, 5, 2, 4, 6)$） 在第四个测试用例中，可以证明不存在这样的排列。 ### 评分规则 1. （3 分）：$a = b = 1, c = n, output = 1$ 2. （8 分）：$n \leq 6, output = 1$ 3. （10 分）：$c = n, output = 1$ 4. （17 分）：$a = 1, output = 1$ 5. （22 分）：$output = 0$ 6. （40 分）：$output = 1$ --- 翻译由 ChatGPT-5 完成