正题

题目链接:https://www.luogu.com.cn/problem/CF835E

题目大意

长度为\(n\)的序列中有两个\(y\)其他都是\(x\)，给出\(n,x,y\)。你每次可以询问一个下标集合的数字异或和，要求在\(19\)次以内找到这两个\(y\)的位置。

\(1\leq n\leq 1000,1\leq x,y\leq 10^9,x\neq y\)

解题思路

考虑询问一个集合我们会得到的答案情况，如果集合大小为奇数则为\(y\)或者\(x\)依次表示\(y\)分别在一个集合内或者都在某个集合中，而偶数则是\(x\ xor\ y\)或者\(0\)。

现在变为了我们可以询问一个集合回答两个\(y\)都在一个集合内或外或者一个在内一个在外。

考虑到两个数字的下标肯定有一个二进制位不同，我们可以枚举这个位然后询问这个位是\(1\)的元素。这样我们总能找到一个集合使得一个\(y\)在内，一个\(y\)在外。

如果在这个两个集合里面暴力问的话算上前面的次数大概是\(3\log n\)的，考虑优化。

发现对于前面的询问，我们可以得到两个集合下标的异或值，所以如果我们问出一个位置再异或出另一个就好了。

因为是\(19\)次所以我们考虑找比较小的那个集合的值就好了。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1100;

int n,x,y,cnt,p[N],ansa,ansb;

void Ask(int l,int r){

	if(l==r){ansa=p[l];return;}

	int mid=(l+r)>>1,ans,flag=0;

	printf("? %d",mid-l+1);

	for(int i=l;i<=mid;i++)

		printf(" %d",p[i]);

	putchar('\n');fflush(stdout);

	scanf("%d",&ans);

	if((mid-l+1)&1)flag=(ans==y);

	else flag=(ans==(x^y));

	if(flag)Ask(l,mid);

	else Ask(mid+1,r);

	return;

}

void Find(int z){

	cnt=0;

	for(int i=1;i<=n;i++)

		if((i/z)&1)p[++cnt]=i;

	if(cnt>(n/2)){

		cnt=0;

		for(int i=1;i<=n;i++)

			if(!((i/z)&1))p[++cnt]=i;

	}

	Ask(1,cnt);

}

int main()

{

	scanf("%d%d%d",&n,&x,&y);

	bool has=0;

	for(int z=1;z<=n;z<<=1){

		int L=0,ans,flag=0;putchar('?');

		for(int i=1;i<=n;i++)if((i/z)&1)L++;

		printf(" %d",L);

		for(int i=1;i<=n;i++)if((i/z)&1)printf(" %d",i);

		putchar('\n');fflush(stdout);

		scanf("%d",&ans);

		if(L&1)flag=(ans==y);

		else flag=(ans==(x^y));

		if(flag&&!has)Find(z),has=1;

		ansb^=z*flag;

	}

	ansb^=ansa;

	if(ansa>ansb)swap(ansa,ansb);

	printf("! %d %d\n",ansa,ansb);

	fflush(stdout);

	return 0;

}

巴特西

CF835E-The penguin‘s game【交互】

正题

题目大意

解题思路

code

最新文章

热门文章