自动搬运

查看原文

来自洛谷，原作者为

	Tairitempest 今天TRTP吃什么？

搬运于2025-08-24 22:47:14，当前版本为作者最后更新于2025-05-09 14:39:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[EGOI 2021] Twin Cookies

本题无需随机化，甚至在 $15$ 次查询内可以通过。

随机配送饼干，选出一些分成两组，他们美味值总和相等。考虑到每次配送饼干是随机的，我们需要让某一次配送饼干的时候所有的选项都可以让它们选出一些分成两组，他们美味值总和相等。

为了方便构造，我们可以让一组只有一个，通过其他的饼干美味值拼凑出一个符合条件的美味值集合，至少有 $N$ 个元素。因为 $N \leq 5000$，因此至少只需要 $13$ 块饼干就能得到一个这样的饼干集合。

稳定通过的实现方法

为了保证可以稳定通过，需要保证任意饼干子集的美味值总和互不相同。通过保证每次选取的饼干美味值都大于以前获得的所有饼干的美味值总和，本次饼干贡献的所有美味值子集总和不会和以前的饼干贡献的所有美味值子集总和有任何交错。

最后拼凑出来的结果很有可能是某个饼干已经询问过的结果。考虑让美味值最小的饼干，其美味值也大于 $N$，然后获取一个美味值极大的饼干（本人使用了 $10^{15}+i,1 \leq i \leq N$）。这样的话我们可以保证美味值极大的饼干贡献的所有美味值子集总和都大于 $10^{15}+N$，自然这些饼干我们是没有询问过的。

因此我们可以在合法的时间复杂度和 $15$ 次询问内解决问题。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

vector<ll> seletc;
vector<ll> out;
vector< array<ll,2> > oknum;
ll n,pos,mv,ans,anspos;

int main(){
	cin>>n;
	pos=n+1;
	for(ll _=0;_<13;_++){
		cout<<'?';
		for(ll __=n;__>0;__--){
			cout<<' ';
			pos++;
			cout<<pos;
		}
		cout<<endl;
		ll tmp;
		cin>>tmp;
		seletc.push_back(tmp);
		pos<<=1;
		pos+=n;
	}
	oknum.push_back({0,0});
	for(ll i=0;i<13;i++)
		for(ll k=0;k<(1<<i);k++)
			oknum.push_back({oknum[k][0]+seletc[i],oknum[k][1]+(1<<i)});
	cout<<'?';
	for(ll i=1;i<=n;i++)
		cout<<' '<<i+(ll)(1e15);
	cout<<endl;
	cin>>mv;
	cout<<'?';
	for(ll i=1;i<=n;i++)
		cout<<' '<<mv+oknum[i][0];
	cout<<endl;
	cin>>ans;
	for(ll i=1;i<=n;i++)
		if(ans-mv==oknum[i][0]) anspos=i;
	ll msk=oknum[anspos][1];
	for(ll k=0;k<13;k++){
		if(msk%2==1) out.push_back(seletc[k]);
		msk/=2;
	}
	cout<<"! 1 "<<out.size()+1<<endl<<ans<<endl<<mv;
	for(ll i:out){
		cout<<' '<<i;
	}
	cout<<endl;
	return 0;
}