题解：P10892 SDOI2024

· · 题解

SDOI2024 题解

前言

update 表。

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

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

做法

如果 $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;
}

其他

代码更好看的版本。