Codeforce Deltix Round, Summer 2021 #D_deltix round, summer 2021 d

Codeforce Deltix Round, Summer 2021 #D

做到的第一个交互题，纪念一下
题目链接

题目大意：已知一个序列有n个数，你需要通过不多于2n次询问来求得这个序列中的第k大的元素

每次询问有两种方式：

or a b 测评机返回在序列中第a位和第b位数的按位或
and a b 测评机返回在序列中第a位和第b位数的按位与

题解：
想要解题我们需要知道一个公式：a+b=a&b+a|b
于是我们可以将第一位的数与其他位数的数进行相加（2n-2次询问）
这时我们再将第二位与第三位的数进行相加（求得2与3的和，两次询问）
这些加和我们用一个a[N]数组来存储（具体见代码）
然后我们就可以将整个序列求出来了
最后sort一遍即可

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;
ll n,k,x;
ll a[N];
int main(){
    cin>>n>>k;
    for(int i=2;i<=n;i++){//2*(n-1)次询问
        cout<<"or 1 "<<i<<endl;cin>>a[i];
        cout<<"and 1 "<<i<<endl;cin>>x;a[i]+=x;//求和
    }
    cout<<"or 2 3"<<endl;cin>>a[0];
    cout<<"and 2 3"<<endl;cin>>x;a[0]+=x;//求2和3的和
    a[1]=(a[2]+a[3]-a[0])/2;//求得1
    for(int i=2;i<=n;i++){
        a[i]-=a[1];//求得每一位数
    }
    sort(a+1,a+1+n);//排序
    cout<<"finish "<<a[k];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22