CF1363D Guess The Maximums 题解

首先我们可以 \(\lceil\log_2n\rceil+1=11\) 次找到数列 \(A\) 的最大值 \(A_p\) 和其位置 \(p\)。然后分讨每个子集是否包含 \(p\)。

对于不包含 \(p\) 的子集，答案就是最大值 \(A_p\)。

接下来考虑包含 \(p\) 的子集。由于子集两两不交，包含 \(p\) 的子集最多只有一个，单独询问一次即可。

这样就可以做到总询问次数 \(\le12\)。

#include <bits/stdc++.h>
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define eb emplace_back
using namespace std;
constexpr int N=1005;
string str;
vector<int> s[N],q;
int ans[N],n,k;
bool f[N];
int query(const vector<int> &vec){int res;cout<<"? "<<vec.size()<<' ';for(int x:vec) cout<<x<<' ';cout<<endl;cin>>res;if(res==-1) exit(1);return res;
}
void solve(){cin>>n>>k;fill(f+1,f+n+1,false);rept(i,1,k){int c,x;cin>>c;s[i].clear();while(c--) cin>>x,s[i].eb(x);}q.clear();rept(i,1,n) q.eb(i);int mx=query(q),l=1,r=n,mid;while(l<r){mid=l+r>>1;q.clear();rept(i,1,mid) q.eb(i);if(query(q)==mx) r=mid;else l=mid+1;}rept(i,1,k){bool suc=false;for(int x:s[i]){if(x==l){suc=true;break;}}if(suc){for(int x:s[i]) f[x]=true;q.clear();rept(i,1,n) if(!f[i]) q.eb(i);ans[i]=query(q);}else ans[i]=mx;}cout<<"! ";rept(i,1,k) cout<<ans[i]<<' ';cout<<endl;cin>>str;
}
signed main(){int T;cin>>T;while(T--) solve();return 0;
}