CF1951H.Thanos Snap

Piotr Rubik - Psalm dla Ciebie

ඞ

有一个长度为 $2^k$ 的数组 $a$，其中 $k$ 是一个正整数，数组 $a$ 初始为 $1$ 到 $2^k$ 的一个排列。Alice 和 Bob 在数组 $a$ 上玩如下游戏。首先，会给 Alice 和 Bob 显示一个值 $t$，其中 $1 \le t \le k$。然后，游戏进行恰好 $t$ 轮，每一轮包括以下操作：

• Alice 可以选择什么都不做，或者选择数组 $a$ 中两个不同的元素并交换它们的位置。
• Bob 选择数组 $a$ 的左半部分或右半部分，并将其擦除。

游戏的得分定义为所有 $t$ 轮操作结束后，数组 $a$ 中的最大值。Alice 希望最大化这个得分，而 Bob 希望最小化它。

你需要输出 $k$ 个数：当 $t$ 从 $1$ 到 $k$ 时，若 Alice 和 Bob 都采取最优策略，游戏的得分分别是多少。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。每个测试用例的描述如下：

第一行包含一个整数 $k$（$1 \le k \le 20$），表示数组 $a$ 的规模参数。

第二行包含 $2^k$ 个整数 $a_1, a_2, \ldots, a_{2^k}$（$1 \le a_i \le 2^k$，$a_i$ 两两不同），表示给定的数组 $a$。

保证所有测试用例中 $2^k$ 的总和不超过 $2^{20}$。

对于每个测试用例，输出 $k$ 个数，第 $i$ 个数表示当 $t = i$ 时，若 Alice 和 Bob 都采取最优策略，游戏的得分。

在第三个测试用例中，当 $t = 2$ 时，游戏可能如下进行：

• 初始时，$a = [5, 1, 6, 4, 7, 2, 8, 3]$。
• Alice 交换 $a_6$ 和 $a_8$，$a$ 变为 $[5, 1, 6, 4, 7, 3, 8, 2]$。
• Bob 擦除数组的右半部分，$a$ 变为 $[5, 1, 6, 4]$。
• Alice 什么都不做，$a$ 保持为 $[5, 1, 6, 4]$。
• Bob 擦除数组的右半部分，$a$ 变为 $[5, 1]$。
• 游戏结束，得分为 $5$。

由 ChatGPT 4.1 翻译