自动搬运

查看原文

来自洛谷，原作者为

	7KByte **

搬运于2025-08-24 22:23:02，当前版本为作者最后更新于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;
}