题解：P12531 [XJTUPC 2025] Beat Verdict: Precision Strike

· · 题解

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;
}