CF1363D Guess The Maximums 做题记录

本题是交互题。

给定长为 $n$ 的数组 $a=[a_1,a_2,...,a_n]$ 和 $k$ 个互不相交的子集 $S_1,S_2,...,S_k$，这些子集中的元素都是 $[1,n]$ 之间的正整数。这些子集两两的交集为空。

你可以进行最多 $12$ 次询问。每次询问你可以给出 $c$ 个互不相同且在 $[1,n]$ 之间的正整数 $v_1,v_2,...,v_c$，然后你会得到 $\max\{v_i\}$。

对于每个子集 $S_i$，你需要求出 $P_i=\max\limits_{j \notin S_i} a_j$。

$1 \leq t \le 10,2 \leq n \leq 1000$，$1 \leq a_i,k \leq n$，$1 \leq c < n$。

诈骗题。

首先二分找到序列中最大值的位置，共需要 $1+\lceil\log n\rceil=11$ 次操作。

观察到子集两两不交，所以最多只有一个子集的最大值不是整个序列的最大值，再询问一次即可。

最多会用 $11+1=12$ 次操作。