题解：P10892 SDOI2024

x1489631649 · 2024-08-21 18:50:47 · 题解

题目链接

分析

因为 1 \le n \le 2^{60}，再乘上操作次数 t（其中 1 \le t \le 5 \times 10 ^ 5），此时的运算次数已经超出了 10^8，所以我们不能通过暴力枚举来完成这道题，然而却没有任何的思路，所以我们就枚举第一个测试点来寻找规律。我们令 step_i(1 \le i \le n) 为题目所求。

1. 当 n = 1 时，显而易见，step_1 = 1。
2. 当 n = 2 时，step_2 = step_1。
3. 当 n = 3 时，我们可以选择将 n 加一或者减一，结果相同。
4. 当 n = 4 时，step_4 = step_2。
5. 当 n = 5 时，step_5 可以等于 step_2 + 1 或者等于 step_3 + 1。我们通过比较可以得到 step_5 = step_2 + 1 的时候更小。
6. 当 n = 6 时，step_6 = step_3。

然后我们总结可得答案等于下表。

显然当 i 是偶数时，我们直接将它除以二，当它为奇数时，我们令 a =\dfrac{i + 1}{2}，再令 b =\dfrac{i - 1}{2}，然后 step_i = \min(a,b) + 1。

可是这是一个递归做法并没有什么差异，所以我们就要继续找规律。

我们将上面得出奇数步数的表列出来。

然后我们就会惊奇的发现 step_a \le step_b。然而这就是我们突破问题的关键，如何证明这个发现不是巧合。

我们从 step_3 开始观察，step_3 就已经大于 step_2，最少也相差一。所以 step_5 会选用 step_2 + 1 然而 step_6 又会等于 step_3，所以 step_5 \le step_6。

所以我们就可以得出以下代码。

Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        long long n,s=0;
        cin>>n;
        while(n!=0)
        {
            if(n%2==0)
                n/=2;
            else{
                s++;
                n/=2;
                if(n%2==1)
                    n++;
            }
        }
        cout<<s<<endl;
    }
}

时间复杂度

时间复杂度为 O(t \log n)，显然可以通过。