CF-1072-C. Huge Pile · znzryb
这道题目没开出来，这把实在打的太唐了。
总结而言，有三点问题：
第一是这个没看榜，还是要经常看榜，观察这个题目的出题速度，人数变化情况，一旦这个人数超过 5000 以上，或者在比赛未过半的时候达到 3000，那么就***说明这道题目就是非常简单***，还是能比较简单的可以**看出来/猜出来的**（就比如说这道题目，这个神秘小性质还是很简单的）。
其实也没有其他问题，div3 的经验我确实比较少，最近打的比较少。
## 题目大意
给定一个包含 N 个苹果的堆，每次可以将一个堆分成两个堆，如果原堆有 x 个苹果，则分成 ⌊x/2⌋ 和 ⌈x/2⌉ 两个堆，每次分堆需要 1 分钟。
问能否通过若干次分堆操作得到一个恰好包含 K 个苹果的堆？如果可以，求最少需要多少分钟。
**输入：**
- 第一行一个整数 t (1 ≤ t ≤ 10⁴)，表示测试用例数量
- 每个测试用例一行两个整数 n 和 k (1 ≤ n, k ≤ 10⁹)，分别表示初始苹果数和目标苹果数
**输出：**
对于每个测试用例，如果无法得到恰好 K 个苹果的堆，输出 -1；否则输出最少需要的分钟数。
## 思路讲解
其实这道题目只需要一个关键结论，就是第 $k$ 步只可能产生 $\lfloor\frac{N}{2^k}\rfloor$ 或者 $\lceil\frac{N}{2^k}\rceil$（当然这两个可能相等）。因此就猜一下就可以了。
当然，利用这个结论，也可以写一个记忆化 bfs，详细地来说，用一个 set 存一下，搜过的数字就不继续搜了。
```cpp
while (!q.empty()) {
auto [x,step]=q.front();
q.pop();
if (x==K) {
cout<<step<<"\n";
return;
}
if (x<K) {
continue;
}
auto res=st.emplace(x/2,step+1);
bool con=!res.second;
if (!con) {
q.emplace(x/2,step+1);
}
res=st.emplace((x+1)/2,step+1);
con=!res.second;
if (!con){
q.emplace((x+1)/2,step+1);
}
}
cout<<-1<<"\n";
```
## AC代码
AC
[https://codeforces.com/contest/2184/submission/357642090](https://codeforces.com/contest/2184/submission/357642090)
::: 源代码
```cpp
/**
* Problem: C. Huge Pile
* Contest: Codeforces Round 1072 (Div. 3)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2184/problem/C
* Created: 2026-01-13 00:11:50
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
struct x_step {
ll x,step;
bool operator<(const x_step & o) const {
if (x!=o.x) return x<o.x;
return step<o.step;
}
x_step(ll x,ll step):x(x),step(step) {
}
};
void Solve() {
ll N,K;
cin >> N >> K;
queue<x_step> q;
q.push({N,0});
set<x_step> st;
while (!q.empty()) {
auto [x,step]=q.front();
q.pop();
if (x==K) {
cout<<step<<"\n";
return;
}
if (x<K) {
continue;
}
auto res=st.emplace(x/2,step+1);
bool con=!res.second;
if (!con) {
q.emplace(x/2,step+1);
}
res=st.emplace((x+1)/2,step+1);
con=!res.second;
if (!con){
q.emplace((x+1)/2,step+1);
}
}
cout<<-1<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2184/submission/357642090
*/
```
:::
## 心路历程（WA，TLE，MLE……）