自动搬运

查看原文

来自洛谷，原作者为

	ChampionCyan Cyan你又压！

搬运于2025-08-24 23:02:14，当前版本为作者最后更新于2024-08-21 19:18:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

SDOI2024 题解

前言

update 表。

赛时猜了一个结论，结果对了（*^▽^*）。然后做完第二题就开始摆烂了。

我感觉写的比官方题解多了四五倍，难道是我太强了是我想复杂了？

做法

$n$ 是偶数不用纠结，直接将 $n$ 赋值为 $\dfrac{n}{2}$ 即可。

如果 $n$ 是奇数，那么先将答案 $+1$，然后分情况讨论：

如果 $\dfrac{n+1}{2}$ 是偶数那么将 $n$ 赋值为 $\dfrac{n+1}{2}$，否则将 $n$ 赋值为 $\dfrac{n-1}{2}$。

证明

作者在比赛时并没有想到证明，证明非常巧妙。结果赛后用了整整三页草稿纸才证明，最后发现官方题解一笔带过。

我们根据选择，有两种情况：

情况一：

我们选择的是 $\dfrac{n+1}{2}(n+1\mod 2=0)$。

我们设 $n=2s-1(s\in \mathbb N^*)$

那么我们 $\dfrac{n+1}{2}=\dfrac{2s-1+1}{2}=s$。

那么为什么 $\dfrac{n-1}{2}(n-1\mod 2=1)$ 一定不比它更优呢？

根据上文 $s$ 的定义，$\dfrac{n-1}{2}=\dfrac{2s-1-1}{2}=s-1$。

明显的，$s$ 和 $s-1$ 必然一奇一偶。

如果此时 $s-1$ 是偶数，那么 $s$ 一定可以通过某种选择使得选择后两种选择以后的 $n$ 是一样的，此时后者（即选择 $\dfrac{n-1}{2}(n-1\mod 2=1)$ ）一定不更优。

否则后者代价再 $+1$ ，又恢复了结果为某两个相差为 $1$ 的正整数。因为两个相差为 $1$ 的正整数后者在 $s-1$ 是偶数的情况下（即选择 $\dfrac{n-1}{2}(n-1\mod 2=1)$ ）一定不更优，而另一种可能又恢复了这种讨论，所以选择的是 $\dfrac{n+1}{2}(n+1\mod 2=0)$ 一定是最优解之一。

情况二

我们选择的是 $\dfrac{n-1}{2}(n-1\mod 2=0)$。

我们设 $n=2s+1(s\in \mathbb N^*)$

那么我们 $\dfrac{n-1}{2}=\dfrac{2s+1-1}{2}=s$。

那么为什么 $\dfrac{n+1}{2}(n+1\mod 2=1)$ 一定不比它更优呢？

根据上文 $s$ 的定义，$\dfrac{n+1}{2}=\dfrac{2s+1+1}{2}=s+1$。

明显的，$s$ 和 $s+1$ 必然一奇一偶。

如果此时 $s+1$ 是偶数，那么 $s$ 一定可以通过某种选择使得选择后两种选择以后的 $n$ 是一样的，此时后者（即选择 $\dfrac{n+1}{2}(n+1\mod 2=1)$ ）一定不更优。

否则后者代价再 $+1$ ，又恢复了结果为某两个相差为 $1$ 的正整数。因为两个相差为 $1$ 的正整数后者在 $s-1$ 是偶数的情况下（即选择 $\dfrac{n+1}{2}(n+1\mod 2=1)$ ）一定不更优，而另一种可能又恢复了这种讨论，所以选择的是 $\dfrac{n-1}{2}(n-1\mod 2=0)$ 一定是最优解之一。

证毕。

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        long long x;
        int ans = 0;
        scanf("%lld", &x);
        while (x) {
            if (x & 1) {
                ans++;
                if (x / 2 % 2)
                    x = x / 2 + 1;
                else
                    x /= 2;
            }
            x >>= 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

其他

代码更好看的版本。