[BalticOI 2020 Day1] 染色

7KByte · 2021-07-15 22:47:33 · 题解

非常有意思的交互题。

隐藏一个常数 C，每次可以查询一个在范围 [1,n] 中的位置，取这个位置和上次查询的位置的差，如果差 \ge C 返回 1，否则返回 0。每个位置只能查询一次。要在 64 次询问内求出答案，1\le C\le N\le 10^{18}。

根据数据范围我们可以知道需要一个严格 \log N 的做法。（多一两次应该没问题

那么只有倍增和二分两个选择。

倍增每次往一个方向走，如果来回走显然会重复位置，看上去就非常不可做。

考虑二分。由于 C 可能很大，那么我们也只有依次向右向左这样来回跳。

到这里我们也没有想到什么好的方法能避免重复询问。

倒着想，最坏的情况我们一定要判断 N-1 是否满足条件，而要判断 N-1 必定是从 1 跳到 N，没有别的选择。

这样我们就知道了最后两次的询问，并且如果卡到最坏情况，显然 C = N，这也就意味着每次二分的返回值都是 0，进一步，每次的 mid 都是固定的。

所以我们可以反推出第一次询问的位置，并且这个位置是唯一的。

从初始位置出发，每次交替向左或向右跳 mid 格即可二分出最终答案。

但是这样做为什么不会有重复的，因为我们倒着推出这个方案是唯一的，其余方案显然会被 C = N 的情况卡掉，所以不会有重复（

感性理解一下，如果一直返回 0 ，就是正的走一遍，一定不会重复。如果某次返回了 1 ，那么范围上界缩小到 mid - 1，在距离当前位置 [l,mid-1] 范围内的格子显然没有走过，归纳一下也没有问题。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define int long long
using namespace std;
vector<int>c;
int ask(int x){
    cout<<"? "<<x<<endl;
    int op;cin>>op;
    return op;
}
signed main(){
    int T;scanf("%lld",&T);
    while(T--){
        int n;scanf("%lld",&n);
        c.clear();
        int l = 1, r = n - 1;
        while(l <= r){
            int mid = (l + r) >> 1;
            c.push_back(mid);
            l = mid + 1;
        }
        reverse(c.begin(), c.end());
        int st = 1, j = 1;
        for(int x : c)st += j * x, j *= -1;
        l = 1, r = n - 1;int ed = n;
        ask(st);
        while(l <= r){
            int mid = (l + r) >> 1;
            st += j * mid, j *= -1;
            if(ask(st))ed = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout<<"= "<<ed<<endl;
    }
    return 0;
}