Codeforces 1365G - Secure Password（思维题）

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\ne 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("\n");

	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]," \n"[i==n]);

	fflush(stdout);

	return 0;

}

巴特西

Codeforces 1365G - Secure Password（思维题）

最新文章

热门文章