专栏文章

题解：CF2155D Batteries

lluuia
CF2155D题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minoqhdw
此快照首次捕获于
2025/12/02 05:52
3 个月前
此快照最后确认于
2025/12/02 05:52
3 个月前
查看原文
这题不是 PKUWC2025 D1T1 吗？

Question

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

Solution

受到上面题的启发，我们考虑把电池分为 rr 个大小尽量均匀的块，那么每个块内两两询问，如果一个块内有超过两个有电的电池，那么我们可以直接得到 11，否则我们知道 aa 一定 ≤r\le r。
因为每个块是尽量均分的，因此我们每次不断合并两个小块为一个大块，这样一次就需要枚举两个小块询问一次。对于一个 rr，我们最坏需要 ⌊n22r⌋\lfloor \frac{n^2}{2r} \rfloor 次询问。
那么我们可以让 r=1,2,4,8,⋯r=1,2,4,8,\cdots 这样的问下去，直到 a>ra > r 我们得到答案。这样做的询问次数是：
∑r⌊n22r⌋≤n22⌈a/2⌉≤⌈n2a⌉\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

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

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...