题解：CF2155D Batteries

· · 题解

这题不是 PKUWC2025 D1T1 吗？

Question

给定 n 个电池，其中有 a 个有电，你每次可以查询两个电池是否同时有电，你需要在不超过 \lceil \frac{n^2}{a} \rceil 次询问中找到两个有电的电池。

Solution

受到上面题的启发，我们考虑把电池分为 r 个大小尽量均匀的块，那么每个块内两两询问，如果一个块内有超过两个有电的电池，那么我们可以直接得到 1，否则我们知道 a 一定 \le r。

因为每个块是尽量均分的，因此我们每次不断合并两个小块为一个大块，这样一次就需要枚举两个小块询问一次。对于一个 r，我们最坏需要 \lfloor \frac{n^2}{2r} \rfloor 次询问。

那么我们可以让 r=1,2,4,8,\cdots 这样的问下去，直到 a > r 我们得到答案。这样做的询问次数是：

\sum_r \left\lfloor \frac{n^2}{2r} \right\rfloor \le \frac{n^2}{2\lceil a/2 \rceil} \le \left\lceil \frac{n^2}{a} \right\rceil

Code

#include<bits/stdc++.h>
using ll = long long;
#define For(i,j,k) for(int i = j;i <= k;i++)
using namespace std;
void sol(){ll n;cin >> n;
    auto qry = [&](ll u,ll v){cout << u << " " << v << endl;
        fflush(stdout);ll o;cin >> o;return o == 1;};
    for(ll i = 1;i < n;i <<= 1) for(ll j = 0;j < n;j += i << 1) For(l,j,min(i + j,n) - 1) 
        For(r,min(i + j,n),min(j + i * 2,n) - 1) if(qry(l + 1,r + 1)) return;
}int main(){ll T;cin >> T;while(T--) sol();return 0;}