CF2150E1 Hidden Single (Version 1)

[AdhesiveWombat - Overdrive](https://soundcloud.com/adhesivewombat/adhesivewombat-overdrive) ⠀ 这道题有两个版本，分别对 $t$、$n$ 以及最大查询次数有不同的限制，解出一个版本不一定能解出另一个。建议同时阅读两个版本。本题不允许 Hack。 这是一个交互题。 有一个长度为 $2n-1$ 的隐藏数组 $a_1, a_2, \ldots, a_{2n-1}$，其中包含 $1$ 到 $n$ 的所有数字，每个数字都恰好出现两次，除了一个只出现一次的数。 你可以进行如下格式的询问，其中 $S$ 是 $\{1, 2, \ldots, 2n-1\}$ 的一个子集，$x$ 是 $[1, n]$ 范围内的整数： - $\texttt{ask(S, x)} $：存在 $i \in S$ 使得 $a_i = x$ 吗？ 请使用不超过 $4n + 2\lceil\log_2 n\rceil$ 次查询，找出只出现一次的那个数字。你只需输出该数字本身，不需要找出它在数组中的位置。 注意，交互器是非自适应的，即隐藏数组在你的查询过程中保持不变。

每个测试点包含多组测试数据。第一行包含测试数据个数 $t$（$1 \le t \le 4000$）。接下来每组测试数据描述如下。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 300$），即隐藏数组 $a_1, a_2, \ldots, a_{2n-1}$ 中的最大值。 保证所有测试点中 $n^2$ 的总和不超过 $4 \times 10^5$。 本题共 80 个测试数据（包括样例）。

（本题为交互题，具体输出格式请参考题目描述与交互说明。）

在第一个测试点中，$n=2$，隐藏数组长度为 $2n-1=3$。一种符合交互的隐藏数组为 $[2, 2, 1]$，其中 $1$ 只出现一次，$2$ 出现两次。 | \# | 选手输出 | 交互器回复 | 解释 | |---|---------|-----------|------| | 1 | ? 1 2 1 2 | 0 | 询问：$a_1=1$ 或 $a_2=1$？否（两者均为 $2$）。因此 $1$ 最多只能出现在位置 $3$，故只出现一次的数字为 $1$。| | 2 | ! 1 | | 输出答案。我们询问了 $1$ 次（输出答案不计入查询次数），少于允许的最多查询次数 $4n + 2\lceil\log_2 n\rceil = 10$。| 在第二个测试点中，$n=3$，隐藏数组长度为 $5$。一种符合交互的隐藏数组为 $[1, 2, 3, 2, 1]$，其中 $3$ 出现一次，$1$ 和 $2$ 各出现两次。 | \# | 选手输出 | 交互器回复 | 解释 | |---|---------|-----------|--------------------------| | 1 | ? 1 2 1 4 1 | 1 | 检查 $a_1$ 或 $a_4$ 是否为 $1$。是（$a_1=1$）。 | | 2 | ? 2 2 1 4 2 | 1 | 检查 $a_1$ 或 $a_4$ 是否为 $2$。是（$a_4=2$）。 | | 3 | ? 2 1 2 | 1 | 检查 $a_2=2$。是。 | | 4 | ? 1 1 5 | 1 | 检查 $a_5=1$。是。 | | 5 | ! 3 | | 可以推断 $3$ 既不出现在 $1$ 和 $4$（其处有 $1$ 和 $2$），也不出现在 $2$ 和 $5$（分别为 $2$ 和 $1$），所以答案为 $3$。| 由 ChatGPT 5 翻译