自动搬运

查看原文

来自洛谷，原作者为

	XuZile 纯纯小萌新一枚

搬运于2025-08-24 23:16:15，当前版本为作者最后更新于2025-06-14 13:09:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12531 题解

解法思路

经过观察可以得知 $x\in [0.5a,2a]$，然而我们至多只能进行 4 次询问，这时我们就可以去考虑使用二分进行分组。我们可以把 $[1,n]$ 分成 16 组，$[1,4][5,20]\cdots[1431655765,5726623060]$，这 16 组分别代表 $2,10\cdots2863311530$。然后用二分算法可以发现不论 $n$ 是多大，最多也只会进行 4 次操作，满足题意。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans,t,n,f[20],L,R;
signed main() {
	cin >> t;
	for(int i = 1 ;i <= 17; i++) f[i] = f[i - 1] * 4 + 1;
	while(t--) {
		cin >> n;
		L = 1;R = 1;
		while (f[R+1] <= n) R++;
		while (L < R){
			int mid = (L + R + 1) / 2;
			printf("? %lld\n",f[mid]);
			int x;
			cin >> x;
			if(x) R = mid - 1;
			else L = mid;
		}
		printf("! %lld\n",min(f[L] * 2,n));
	}
	return 0;
}