非常有意思的交互题。
隐藏一个常数 \(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; }