CF1363D Guess The Maximums 题解

题意简述

有一个含有 $n$ 个数字的数组 $a$（$n\le1000$），有 $k$ 个不重合的集合 $S_1,S_2,\cdots,S_k$，集合元素为 $1$ 到 $n$ 的整数，由此生成一个长度为 $k$ 的密码 $p$，定义 $p_i=\displaystyle\max_{j\notin S_i}a_j$，允许进行至多 $12$ 次询问猜出密码，每次询问一个集合 $S_0$，返回 $\displaystyle\max_{i\in S_0}a_i$。

思路分析

注意到 $S_i$ 不交，因此除了包含的所有最大元素的集合外（这样的集合不一定存在），其他所有位置的密码都是最大值，因此这道题包含两个步骤：

1. 找到最大值；
2. 找到含最大值一组的答案。

对于第一个步骤，只要询问 $1$ 到 $n$ 的答案即可，对于第二个步骤，可以再分为两步：

1. 找到最大值所在的集合；
2. 找到这个集合的答案。

对于第一个步骤，结合次数限制，容易想到二分查找。具体的，先假设最大值只有一个（之后解释正确性），每一次询问当前区间的一半，检查结果是否等于最大值，确定最大值在哪一半，缩小范围直到找到最大值，再找到最大值所在的集合编号。

对于第二个步骤，按照题目描述查询除去最大值所在集合即可。

正确性分析

1. 询问次数不超过 $12$

   分析所有的询问，步骤 $1$ 花费 $1$ 次查询，步骤 $2.1$ 花费至多 $\log_21000=10$ 次查询，步骤 $2.2$ 花费 $1$ 次查询，总共至多 $12$ 次查询。

2. 假设最大值只有一个不会影响结果

   考虑有多个最大值的情况：若所有最大值都在同一集合，则最后找到的最大集合无误；若最大值在不同集合，则所有的答案都是最大值，无论找到哪个集合都不影响。

易错提醒

1. 注意处理最大值为不属于任何集合的情况。
2. 一定要清空（也是为了应对不属于任何集合的元素），否则 $\color{red}\text{ILE on test 7}$。

代码实现

不要进行没有意义的抄袭。

int num[2005],idx[2005];
int n,k;
void solve(){
    cin>>n>>k;
	for(int i=1;i<=n;i++){
		num[i]=idx[i]=0;
	}
    (num,idx)=INPUT();
	int l=1,r=n;
	int mx,pos;
    mx=ASK(1~n);
	while(l<=r){
		int mid=(l+r)/2;
		int ans;
        ans=ASK(l~mid);
		if(ans==mx){
			r=mid-1;
			pos=mid;
		}
		else{
			l=mid+1;
		}
	}
    //ASK THE DIFFERENT SET
	cout<<"? "<<n-num[idx[pos]]<<" ";
	for(int i=1;i<=n;i++){
		if(idx[i]!=idx[pos]||idx[pos]==0){
			cout<<i<<" ";
		}
	}
	cout<<endl;
	int ans;
	cin>>ans;
    //ANSWER
	cout<<"! ";
	for(int i=1;i<=k;i++){
		if(idx[pos]==i){
			cout<<ans<<" ";
		}
		else{
			cout<<mx<<" ";
		}
	}
	cout<<endl;
	string result;
	cin>>result;
}