CF-1072-C. Huge Pile

这道题目没开出来，这把实在打的太唐了。

总结而言，有三点问题：

第一是这个没看榜，还是要经常看榜，观察这个题目的出题速度，人数变化情况，一旦这个人数超过 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 存一下，搜过的数字就不继续搜了。

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

源代码

/**
 * 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……）