洛谷 P1582 倒水

// P1582 ★ 暴力：一个一个试 z —— 答案永远正确，问题只在「跑不跑得完」
//
// ★★ 「O(答案) 的暴力肯定超时」是一句要**乘一遍**才能说的话
//   （[第 40 章 P1372](/sol/p1372/)、[第 41 章那三次](/sol/p1217/)都被打回过）。
//   这道题的最坏形状是 **N = 2³⁰+1、K = 1** ⇒ z = 1073741823，约 **10.7 亿次**循环，
//   而循环体只有「加一 + 一条 popcnt 指令 + 一次比较」。
//   ⇒ 到底够不够，见 p1582Count.cpp 那一行实测。
#include <cstdio>
using namespace std;

int main() {
    long long n, k;
    if (scanf("%lld %lld", &n, &k) != 2) return 0;
    long long z = 0;
    while (__builtin_popcountll(n + z) > k) z++;
    printf("%lld\n", z);
    return 0;
}

// P1582 倒水 —— 正解：答案就是「最小的 z，使得 popcount(N+z) ≤ K」
//
// ★★ 两步推理，第一步是题目、第二步才是位运算：
//   ① **最后剩几个瓶子 = popcount(总水量)。**
//      每次合并把两个相同的水量并成它的两倍 ⇒ 每个瓶子里的水量永远是 2 的幂；
//      总水量 n 固定 ⇒ 最少能剩几个瓶子 = 「把 n 写成若干个 2 的幂之和，最少要几项」
//      = n 的二进制里有几个 1 = **popcount(n)**（这就是二进制表示唯一性）。
//   ② 买 z 个新瓶子 ⇒ 总水量变成 n + z ⇒ 问的就是「最小的 z 使 popcount(n+z) ≤ K」。
//
// ★★★ 而第 ② 步的高效解法是一行 lowbit：**n += lowbit(n)**。
//   加上最低位那个 1，会让最低的那一段连续的 1 进位并成更高的一个 1
//   ⇒ popcount 不会变大，而**最低位那个 1 的位置严格上升** ⇒ 最多走 31 步就到 2 的幂。
//   （[第 46 章第 9 步](/ch/46-bitwise/)证过 `lowbit(x) = x & -x`。）
//
// ⚠⚠ 类型这一笔要单独算：N ≤ 2×10⁹ **装得进 int**（余量 7.37%），答案也装得进，
//   ⇒ 唯一装不下的是**中间值** —— N 顶格而 K = 1 时要走到 2³¹ = 2147483648。
//   ⇒ [「答案装得下、中间值装不下」](/sol/p1044/)的又一个现场，而这次连答案都装得下。
#include <cstdio>
using namespace std;

int main() {
    long long n, k;
    if (scanf("%lld %lld", &n, &k) != 2) return 0;
    long long m = n;
    while (__builtin_popcountll(m) > k) m += m & (-m);   // ★ 加上 lowbit
    printf("%lld\n", m - n);
    return 0;
}

// P1582 ★ 验算走一条和位运算完全无关的路：**真的把水倒一遍**
//   ./p1582Sim [上限 n]     默认 28
//   ./p1582Sim [上限 n] csv
//
// ★★★ 为什么需要它：正解和暴力（p1582Brute）**共享同一个前提** ——
//   「最少剩几个瓶子 = popcount(总水量)」。两份代码都建立在这句话上，
//   所以它们互相对拍**验的是零**（[第 37 章 P2085](/sol/p2085/) 那条：
//   参照物和解法共享一个假设，这个对拍什么都没验）。
//
// ⇒ 这一份不用 popcount，也不用二进制：它从「n 个 1 升的瓶子」出发，
//   **BFS 枚举所有可达的状态**（每一步：挑两个水量相同的瓶子并成一个），
//   记录能达到的最少瓶子数，再和 popcount(n) 比。
//   —— 两条路一行代码都不共享。
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    int NMAX = argc > 1 ? atoi(argv[1]) : 28;
    bool csv = (argc > 2 && argv[2][0] == 'c');

    int bad = 0, checked = 0, badSelf = 0;   // badSelf：拿一个**已知错**的说法（「最少恒为 1」）验这段代码是活的
    string detail;
    for (int n = 1; n <= NMAX; n++) {
        vector<int> start(n, 1);
        set<vector<int>> seen;
        queue<vector<int>> q;
        seen.insert(start); q.push(start);
        int best = n;
        while (!q.empty()) {
            vector<int> cur = q.front(); q.pop();
            best = min(best, (int)cur.size());
            for (size_t i = 0; i + 1 < cur.size(); i++)
                if (cur[i] == cur[i + 1]) {                 // 有序 ⇒ 相等的必然相邻
                    vector<int> nx;
                    for (size_t j = 0; j < cur.size(); j++)
                        if (j != i && j != i + 1) nx.push_back(cur[j]);
                    nx.push_back(cur[i] * 2);
                    sort(nx.begin(), nx.end());
                    if (seen.insert(nx).second) q.push(nx);
                }
        }
        int pc = __builtin_popcount((unsigned)n);
        checked++;
        if (best != pc) { bad++; if (detail.size() < 60) detail += to_string(n) + " "; }
        if (best != 1) badSelf++;                       // ⚠ 自检：这一行必须**不是** 0
    }

    if (csv) {
        printf("checked,%d\nbad,%d\nbadSelf,%d\n", checked, bad, badSelf);
        return 0;
    }
    printf("P1582 的立论「最少剩几个瓶子 = popcount(总水量)」——真把水倒一遍验一遍\n\n");
    printf("  n = 1 .. %d 全枚举（BFS 所有可达状态，不用任何位运算）\n", NMAX);
    printf("  和 popcount(n) 对不上的：%d 个 %s\n", bad, bad ? detail.c_str() : "");
    printf("  ⚠ 自检：同一段 BFS 去验一个**已知错**的说法（「最少恒为 1 瓶」）—— 对不上 %d 个\n", badSelf);
    printf("\n  ⇒ 这条路和正解、和暴力都不共享任何前提 —— 它验的是「题目 → popcount」那一步本身。\n");
    return 0;
}

// P1582 解析页上所有数字的出处。
//   ./p1582Count          人话版
//   ./p1582Count csv      给 check:viz 用
//
// 四件事：
//   ① ★★ **lowbit 那个循环最多走几步** —— 用「最低位那个 1 的位置严格上升」证得 ≤ 31，
//      这里把 N = 1..2×10⁹ 抽样 + 把「交替 1」这类最坏形状算一遍，看实测最大是多少。
//   ② ★★★ **暴力（一个一个试 z）到底够不够** —— 「O(答案) 肯定超时」是要乘一遍才能说的话
//      （[第 40 章 P1372](/sol/p1372/) 打回过一次）。这里用**步数**这把机器无关的尺子量，
//      秒表只当量级（硬规矩第 5 条）。
//   ③ 类型账：`int` 在这道题上「输入够、答案够、中间不够」。
//   ④ 两个错法的触发线，以及三组官方样例各挡住了谁。
#include <bits/stdc++.h>
#include <chrono>
using namespace std;

static long long solveOk(long long n, long long k, long long* steps = nullptr) {
    long long m = n, s = 0;
    while (__builtin_popcountll(m) > k) { m += m & (-m); s++; }
    if (steps) *steps = s;
    return m - n;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && argv[1][0] == 'c');
    const long long NMAX = 2000000000LL;

    /* ---------- ① lowbit 循环最多走几步 ---------- */
    long long maxSteps = 0, argN = 0;
    mt19937_64 rng(20260906ull);
    for (int i = 0; i < 3000000; i++) {
        long long n = 1 + (long long)(rng() % (unsigned long long)NMAX);
        long long s; solveOk(n, 1, &s);
        if (s > maxSteps) { maxSteps = s; argN = n; }
    }
    /* 「交替 1」那种最坏形状：0b0101…01 */
    long long alt = 0; for (int b = 0; b <= 30; b += 2) if ((1LL << b) <= NMAX) alt |= 1LL << b;
    long long altSteps; solveOk(alt, 1, &altSteps);

    /* ---------- ② 暴力够不够：先算步数，再量秒表 ---------- */
    /* ⚠⚠ 这两个数必须是**运行期**才知道的值：写成编译期常量的话，-O2 会把整个循环算穿
       （[第 42 章 P1965](/sol/p1965/) 那一跤：第一版量出 254 毫秒，真值 1310 毫秒，差 5.2 倍）。*/
    volatile long long vN = (1LL << 30) + 1, vK = 1;
    long long worstN = vN, worstK = vK;                      // 最坏形状：z 最大
    long long okSteps; long long z = solveOk(worstN, worstK, &okSteps);
    /* ⚠ 结果必须落进 volatile，否则 -O2 会把整个循环当死代码删掉
       （[第 45 章 ops.cpp](/ch/45-estimate/) 同款；第一版量出 0 毫秒就是栽在这儿）。*/
    static volatile long long sink = 0;
    auto t0 = chrono::steady_clock::now();
    long long zz = 0; while (__builtin_popcountll(worstN + zz) > worstK) zz++;
    sink = zz; (void)sink;
    double bruteMs = chrono::duration<double, milli>(chrono::steady_clock::now() - t0).count();

    /* ---------- ③ 类型账 ---------- */
    double intMargin = 2147483647.0 / (double)NMAX;
    long long midMax = 1LL << 31;                            // 顶格时中间值要走到 2³¹
    long long ansMax = z;                                    // 答案的顶格

    /* ---------- ④ 触发线 / 官方样例 ---------- */
    struct S { long long n, k; } sam[3] = {{3, 1}, {13, 2}, {1000000, 5}};
    string powHit, doHit;
    for (int i = 0; i < 3; i++) {
        long long a = solveOk(sam[i].n, sam[i].k);
        long long p = solveOk(sam[i].n, 1);                              // ✗ 把 K 当成 1
        long long m = sam[i].n; long long d = m & (-m);                  // ✗ do…while
        m += d; while (__builtin_popcountll(m) > sam[i].k) m += m & (-m);
        powHit += (p == a ? '.' : 'X');
        doHit  += (m - sam[i].n == a ? '.' : 'X');
    }
    /* K ≥ 31 时答案恒为 0（N ≤ 2×10⁹ < 2³¹ ⇒ popcount ≤ 31）*/
    /* ★ 这个不用抽样，能精确算：把 M 的某一个 1 改成 0、它下面全填 1，取最大的 popcount */
    long long maxPop = __builtin_popcountll(NMAX);
    for (int b = 0; b <= 31; b++) if (NMAX >> b & 1) {
        long long cand = (NMAX & ~((1LL << (b + 1)) - 1)) | ((1LL << b) - 1);
        if (cand >= 1) maxPop = max(maxPop, (long long)__builtin_popcountll(cand));
    }

    if (csv) {
        printf("maxSteps,%lld\n", maxSteps);
        printf("altSteps,%lld\n", altSteps);
        printf("okSteps,%lld\n", okSteps);
        printf("bruteZ,%lld\n", z);
        printf("stepRatio,%lld\n", z / max(1LL, okSteps));
        printf("bruteBand,%d\n", (bruteMs > 300.0 && bruteMs < 8000.0) ? 1 : 0);
        printf("intMargin,%.4f\n", intMargin);
        printf("midMax,%lld\n", midMax);
        printf("ansMax,%lld\n", ansMax);
        printf("intFitsN,%d\n", NMAX < 2147483647LL ? 1 : 0);
        printf("intFitsAns,%d\n", ansMax < 2147483647LL ? 1 : 0);
        printf("intFitsMid,%d\n", midMax < 2147483647LL ? 1 : 0);
        printf("powHit,%s\n", powHit.c_str());
        printf("doHit,%s\n", doHit.c_str());
        printf("maxPop,%lld\n", maxPop);
        return 0;
    }

    printf("P1582：答案 = 最小的 z 使 popcount(N+z) ≤ K\n\n");
    printf("  ① lowbit 循环走几步：抽样 300 万个 N（K=1）最多 %lld 步（N = %lld）；\n", maxSteps, argN);
    printf("     「交替 1」那种最坏形状 %lld 走 %lld 步。上界 31 是证出来的。\n\n", alt, altSteps);
    printf("  ② 暴力（一个一个试 z）最坏形状 N = %lld、K = %lld：\n", worstN, worstK);
    printf("     答案 z = %lld ⇒ 循环 %lld 次，实测 %.0f 毫秒（时限 1 秒）\n", z, z, bruteMs);
    printf("     而正解只走 %lld 步 ⇒ 步数差 %lld 倍\n\n", okSteps, z / max(1LL, okSteps));
    printf("  ③ int 这笔账：N 顶格 %lld < 2147483647（余量 %.2f%%）✓；答案顶格 %lld ✓；\n",
           NMAX, (intMargin - 1) * 100, ansMax);
    printf("     ⚠ 而中间值要走到 %lld ✗ ——「两头都够，中间不够」\n\n", midMax);
    printf("  ④ 三组官方样例（. = 放过，X = 一测就死）：把 K 当成 1 → %s；do…while → %s\n",
           powHit.c_str(), doHit.c_str());
    printf("     N ≤ 2×10⁹ 里 popcount 最大是 %lld（精确算的）⇒ K ≥ %lld 时答案恒为 0\n", maxPop, maxPop);
    return 0;
}