Codeforces 1365G

Codeforces 题面传送门 & 洛谷题面传送门

首先考虑一个询问 (20) 次的方案,考虑每一位,一遍询问求出下标的这一位上为 (0) 的位置上值的 bitwise or,再一遍询问求出下标的这一位上为 (1) 的位置上值的 bitwise or,然后这一位上为 (0) 的位置对这一位上为 (1) 的位置产生对应的贡献,同理这一位上为 (1) 的位置对这一位上为 (0) 的位置产生对应的贡献。

这个询问次数显然无法通过。注意到这个 (13) 的限制给得比较奇怪,并且有 (dbinom{13}{6}=1716>1000)。因此考虑将每个位置赋上一个 ([0,8191]) 且二进制下恰好包含 (6)(1) 的编号,然后第 (i) 次询问编号的第 (i) 位上为 (1) 的位置的 bitwise or,然后更新编号第 (i) 位上为 (0) 的位置的答案即可。注意到每个数的编号不存在包含关系,因此对于任意两个 (i e j),必然存在某一位 (k) 满足 (i)(k) 位为 (0),而 (j)(k) 位为 (1),这样任意两对不同的数都会对对方产生贡献了。

const int MAXN=1716;
int n,msk[MAXN+5],mcnt=0;
ll res[MAXN+5];
void ask(vector<int> v){
	if(v.empty()) return;
	static bool vis[MAXN+5];
	printf("? %d",v.size());memset(vis,0,sizeof(vis));
	for(int x:v) printf(" %d",x),vis[x]=1;printf("
");
	fflush(stdout);ll val;scanf("%lld",&val);
	for(int i=1;i<=n;i++) if(!vis[i]) res[i]|=val;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<8192;i++) if(__builtin_popcount(i)==6)
		msk[++mcnt]=i;
	for(int i=0;i<13;i++){
		vector<int> v;
		for(int j=1;j<=n;j++) if(msk[j]>>i&1) v.pb(j);
		ask(v);
	} printf("! ");
	for(int i=1;i<=n;i++) printf("%lld%c",res[i]," 
"[i==n]);
	fflush(stdout);
	return 0;
}
原文地址:https://www.cnblogs.com/ET2006/p/Codeforces-1365G.html