题解：P10892 SDOI2024

RainPPR · 2024-08-21 19:05:14 · 题解

本质和 STD 类似，使用了不同的比较方式。

对正确性进行了口嗨的证明，如果您认为证明有不严谨的或者不正确，欢迎私信交流。

注意从低到高考虑每一个二进制位，遇到 1 会导致答案 +1。

因此，我们每次可以选择的数中，应当选择一个 1 数量最少的。

考虑这么贪心的做，为什么是对的，但是先上 AC 代码。

using ll = long long;

#define int ll
#define popcnt(x) __builtin_popcount(x)

int Calc(int n) {
    int ans = 0;
    while (n) {
        n >>= __builtin_ctzll(n);
        int t1 = n >> 1, t2 = t1 + 1;
        n = (popcnt(t1) < popcnt(t2)) ? t1 : t2;
        ++ans;
    }
    return ans;
}

也就是两个决策点，

t_1=\left\lfloor\dfrac{n}{2}\right\rfloor

t_2=\left\lfloor\dfrac{n}{2}\right\rfloor+1

注意到我们每次两个决策，是相差 1 的。

那么区别就在于 t_1 的最后的连续的 1 的区间。

t_1=(\dots0\underline{11\dots11})_2

t_2=(\dots1\underline{00\dots00})_2

注意到我们如果继续对 t_1,t_2 分别继续消除，

将 t_1 的最后连续的 1 和前面的 0 消除至少需要两次。
将 t_2 的最后连续的 0 和前面的 1 消除只需要一次。

注意到这两种消法，都能创造出相同的，前面省略号的内容，分别为，

将 t_1 末尾消去，然后加一，直到前面新增的 1 处可以两种决策；
将 t_2 一直消去，直到前面的 1，然后同样两种相同的决策可以得到一样的结果。

因此，我们证明了这么贪心是正确的。

然后你注意到这两个一定是一个奇数一个偶数，

那么用奇偶性比较，就是 STD 的贪心方式了（x