题解：P10892 SDOI2024

xin_xin_xin · 2024-08-22 10:43:13 · 题解

阅读题目可知

针对题目我们要求出AzureHair的最小纠结次数也就是（剩余猫猫为奇数的最少次数），于是我们可以得到以下规律。

1.当前猫猫数减去（n+1）/2的猫猫数为偶数—— (n-(n+1)/2)%2==0

2.当前猫猫数减去（n-1）/2的猫猫数为偶数—— (n-(n-1)/2)%2==0

3.如果均成立则任意减去（本人偏多减），如果均不成立则也可以任意减去前两条之一。
AC代码如下

#include<bits/stdc++.h>//万能头是好东西，不知道的可以学一下，不过万能头比正常的3毫秒，小心卡时间 
using namespace std;
#define ll unsigned long long int//养成好习惯，不会卡数据，暴了别忘调 
ll n,m,k,x;//优先设好需要使用的字母  
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;//输入 
    for(int i=1;i<=n;i++){
        cin>>x;
        k=0;//初始化很重要，不然爆零两行泪 
        while(x>0){
            if(x%2!=0){//为奇数的情况 
                k++;//进行累加 
                if((x-(x+1)/2)%2==0) x=x-(x+1)/2;//规律一成立 
                else if((x-(x-1)/2)%2==0) x=x-(x-1)/2;//规律二成立 
                else x=x-(x+1)/2;//规律三成立 
            }
            else x=x/2;//为偶数无脑直接除2 
        }
        cout<<k<<endl;//循环内输出结果，位置要放对 
    }
    return 0;
} //完美结束完结撒花 

题解不易，多多支持，感谢