题解：P10892 SDOI2024

别人内卷我在躺平 · 2024-08-21 18:46:34 · 题解

题目意思很简单，其实就是让我们去模拟：
如果 n 是奇数，纠结次数 cnt 就要 +1，然后就要去比较:

• 由于题目让我们求最小纠结次数，所以我们每次都要让猫的只数 n 尽量为偶数。
• 如果 n-\frac{n-1}{2} 是偶数，那么 n=n-\frac{n-1}{2}。
• 如果 n-\frac{n+1}{2} 是偶数，那么 n=n-\frac{n+1}{2}。
• 由于 n 为奇数，所以 n+1 和 n-1 都是偶数，即相邻两个数。
  否则是偶数，直接将 n 减去一半就行了。

代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
       //一定要开 long long
    unsigned long long t;
    cin>>t;
    while(t--)
    {
        unsigned long long n;
        cin>>n;//输入
        unsigned long long cnt=0;
        while(n>0)//当猫的只数>0的时候，就还可以拿出猫
        {
            if(n%2==1)//如果n是奇数
            {
                unsigned long long a=(n-1)/2;//计算要拿出的只数
                unsigned long long b=(n+1)/2;//同理
                unsigned long long c=n-a;//算出还剩几只猫
                unsigned long long d=n-b;//同理
                if(c%2==0) n=n-a;//如果拿出(n-1)/2只可以，那么n就减去(n-1)/2。
                else if(d%2==0) n=n-b;//如果拿出(n+1)/2只可以，那么n就减去(n+1)/2。
                cnt++;//纠结次数别忘了+1。
            }
            else
            {
                n=n/2;//如果n是偶数,n=n/2就行了
            }
        }
        cout<<cnt<<"\n";//输出并换行
    }
    return 0; 
} 

注意:由于 n≤2^{60},所以要开 long long!