CF2150E1.Hidden Single (Version 1)

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 翻译