[数据结构与算法]Codeforces 1556 D. Take a Guess（1800，交互题）

链接：https://codeforces.com/contest/1556/problem/D

题意：

有一个序列，你需要机器猜，可以询问不超过2 ? n个问题，两个下标为i和j的项按位与( i ≠ j )的结果是什么？??两个下标为i和j的项按位或( i ≠ j )的结果是什么?你需要找到第k 小数；

题解：

只要知道a + b = a & b + a ∣ b （自己推一下，很快），然后就可以经过n-1次的询问知道a1+a2,a2+a3,a3+a4.....an-1+an;再只要知道随便一对结果，就可以求出所有的数(这边我取a1+a3的值);一共n次询问，然后所有数排序，输出第k大的；具体实现看代码；

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


ll num[1010000];
ll ans[1010000];

int main()
{
    ll n, k;
    cin >> n >> k;
    for (int i = 1; i <= n-1; i++)
    {
        cout << "and " << i << " " << i + 1 << endl;
        int x;
        cin >> x;
        cout << "or " << i << " " << i + 1 << endl;
        int y;
        cin >> y;
        num[i] = ll(x) + y;
    }
    cout << "and " << 1 << " " <<3<< endl;
    int x1;
    cin >> x1;
    cout << "or " << 1 << " " << 3 << endl;
    int y1;
    cin >> y1;
    //x1+y1=(ans1+ans3);
    ans[1] = (ll(x1) + y1 - num[2] + num[1]) / 2;
    for (int i = 1; i <= n - 1; i++)
    {
        ans[i + 1] = num[i] - ans[i];
    }
    sort(ans + 1, ans + n+1);
    cout << "finish " << ans[k] << endl;
    return 0;
}