CF1492B Card Deck

你有一副包含 $n$ 张牌的牌堆，你希望将其重新排列成一个新的牌堆。 每张牌的数值为 $1$ 到 $n$ 之间的某个整数，记为 $p_i$。所有 $p_i$ 两两不同。牌堆中的牌从下到上编号，即 $p_1$ 表示最底下的牌，$p_n$ 表示最顶上的牌。 每一步操作，你可以选择一个整数 $k > 0$，从原牌堆的顶部取出 $k$ 张牌，保持它们的顺序，将它们放到新牌堆的顶部。你可以重复进行该操作，直到原牌堆为空。（具体操作可参考题目说明部分。） 我们定义一个牌堆的序为 $ \sum\limits_{i = 1}^{n}{n^{n - i} \cdot p_i} $。 给定原始牌堆，请输出通过上述操作能够得到的序最大的牌堆。输出新牌堆从底到顶的牌面数值。 如果有多种方案，输出任意一种即可。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示牌堆的大小。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$，且 $i \neq j$ 时 $p_i \neq p_j$），表示从底到顶的牌面数值。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一行，表示通过操作得到的序最大的牌堆，从底到顶输出牌面数值。 如果有多种方案，输出任意一种。

在第一个测试用例中，一种最优策略如下： 1. 从 $p$ 顶部取 $1$ 张牌放到 $p'$ 顶部：$p$ 变为 $[1, 2, 3]$，$p'$ 变为 $[4]$； 2. 再取 $1$ 张牌放到 $p'$ 顶部：$p$ 变为 $[1, 2]$，$p'$ 变为 $[4, 3]$； 3. 再取 $1$ 张牌放到 $p'$ 顶部：$p$ 变为 $[1]$，$p'$ 变为 $[4, 3, 2]$； 4. 再取 $1$ 张牌放到 $p'$ 顶部：$p$ 变为空，$p'$ 变为 $[4, 3, 2, 1]$。 最终，$p'$ 的序为 $4^3 \cdot 4 + 4^2 \cdot 3 + 4^1 \cdot 2 + 4^0 \cdot 1 = 256 + 48 + 8 + 1 = 313$。 在第二个测试用例中，一种最优策略如下： 1. 从 $p$ 顶部取 $4$ 张牌放到 $p'$ 顶部：$p$ 变为 $[1]$，$p'$ 变为 $[5, 2, 4, 3]$； 2. 再取 $1$ 张牌放到 $p'$ 顶部：$p$ 变为空，$p'$ 变为 $[5, 2, 4, 3, 1]$。 最终，$p'$ 的序为 $5^4 \cdot 5 + 5^3 \cdot 2 + 5^2 \cdot 4 + 5^1 \cdot 3 + 5^0 \cdot 1 = 3125 + 250 + 100 + 15 + 1 = 3491$。 在第三个测试用例中，一种最优策略如下： 1. 从 $p$ 顶部取 $2$ 张牌放到 $p'$ 顶部：$p$ 变为 $[4, 2, 5, 3]$，$p'$ 变为 $[6, 1]$； 2. 再取 $2$ 张牌放到 $p'$ 顶部：$p$ 变为 $[4, 2]$，$p'$ 变为 $[6, 1, 5, 3]$； 3. 再取 $2$ 张牌放到 $p'$ 顶部：$p$ 变为空，$p'$ 变为 $[6, 1, 5, 3, 4, 2]$。 最终，$p'$ 的序为 $6^5 \cdot 6 + 6^4 \cdot 1 + 6^3 \cdot 5 + 6^2 \cdot 3 + 6^1 \cdot 4 + 6^0 \cdot 2 = 46656 + 1296 + 1080 + 108 + 24 + 2 = 49166$。 由 ChatGPT 4.1 翻译