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

dongzirui0817 · 2025-05-20 20:59:03 · 题解

思路

发现 [0.5n, \, 2n] 的范围中，在 x 很大时会包含很多数，所以考虑将一个区间的数用一个代表记下，这个范围的数在输出代表时均满足。

于是得到如下表格：

事实上不看表格也行。

总之，设第 i 个区间代表为 f_i，那么 f_1 = 2，f_i = (2 \times f_{i - 1} + 1) \times 2，对应区间为 [0.5f_i, \, 2f_i]。

然后你发现刚好 16 个区间，用二分刚好就能在 4 次询问内解决。

然后，就没有然后了。

思路

先预处理代表 f_i，之后每一次测试二分。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll c[20];
int T;

int main() {
    c[1] = 2;
    for (int i = 2 ; i <= 16 ; i++)
        c[i] = (c[i - 1] * 2 + 1) * 2;
    for (int i = 1 ; i <= 16 ; i++)
        printf("%lld %lld %lld\n", c[i] / 2, c[i], c[i] * 2);
    cin >> T;
    for (ll n ; T-- ; ) {
        cin >> n;
        int L = 1, R = 2;
        for (int i = 1 ; i <= 16 ; i++)
            if (c[i] * 2 < n) ++R;
        while (L < R - 1) {
            int mid = (L + R) >> 1, k;
            cout << "? " << c[mid] / 2 << endl;
            cin >> k;
            if (k) R = mid;
            else L = mid;
        }
        if (c[L] > n) cout << "! " << n << endl;
        else cout << "! " << c[L] << endl;
    }
    return 0;
}