正题
题目链接:https://codeforces.com/contest/1556/problem/D
题目大意
现在有(n)个你不知道的数字,你有两种询问操作
- 询问两个下标的数字的(and)
- 询问两个下标的数字的(or)
要求在(2n)次操作以内求出第(k)小的数字
(1leq nleq 10^4,0leq a_ileq 10^9)
解题思路
显示我们取(and)之后为(0)且(or)之后为(1)的位就可以得到两个数字的异或,所以我们可以通过(2n-2)次询问得到所有数字之间的异或值,那么此时我们就只需要知道一个数字就可以得到其他所有的。
然后考虑怎么求某一个数字,我们前面的步骤中拿(1)去(or)和(and)其他所有的值,不难发现每次我们除了知道异或值还能确定这两个数字异或之后为(0)的位上的具体值。
那么我们不知道位的肯定是(1)和其他所有数字都不同的,也就是这些位上除了(1)其他数字都相同,那么我们直接拿另外两个数(and/or)一下再取这些位上的值就好了。
这样询问次数就是(2n-1)次,可以通过本题。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int n,k,a[N],p[N];
int main()
{
scanf("%d%d",&n,&k);
int MS=(1<<30)-1,ans=0,bns=0;
for(int i=2,x,y;i<=n;i++){
printf("and 1 %d
",i);
fflush(stdout);
scanf("%d",&x);
printf("or 1 %d
",i);
fflush(stdout);
scanf("%d",&y);y^=MS;
p[i]=(MS^(x|y));
ans|=x;bns|=y;
}
int c=MS^(ans|bns),cns;
printf("and 2 3
");
fflush(stdout);
scanf("%d",&cns);cns&=c;
a[1]=(c^cns)|ans;
for(int i=2;i<=n;i++)a[i]=a[1]^p[i];
sort(a+1,a+1+n);
printf("finish %d
",a[k]);
fflush(stdout);
return 0;
}