CF1363D Guess The Maximums 做题记录

本题是交互题。

给定长为 nn 的数组 a=[a1,a2,...,an]a=[a_1,a_2,...,a_n]kk 个互不相交的子集 S1,S2,...,SkS_1,S_2,...,S_k,这些子集中的元素都是 [1,n][1,n] 之间的正整数。这些子集两两的交集

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

对于每个子集 SiS_i,你需要求出 Pi=maxjSiajP_i=\max\limits_{j \notin S_i} a_j

1t10,2n10001 \leq t \le 10,2 \leq n \leq 10001ai,kn1 \leq a_i,k \leq n1c<n1 \leq c < n

诈骗题。

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

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

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