题目背景
AzureHair 在 NOIP 2022 中被喵了个喵创死，于是患上了不治之症——T2 恐惧症，于是他在 NOIP 2023 中果断跳过了 T2 并杠 T3 两小时无果，遗憾离场，他的同学决定帮他治疗这种不治之症。
在他的同学给他治愈了 T2 恐惧症后，他自信的开始了他的 SDOI，遂分讨写了 22 个小时没写出来，遗憾离场……
题目描述
AzureHair 的同学把 AzureHair 和 n 只猫猫关在一个房间里，并且要求 AzureHair 每过一天就交出 n/2 只猫猫，但是如果 n 是奇数时，AzureHair 就会纠结于要交出 (n+1)/2 只猫猫还是交出 (n−1)/2 只猫猫。AzureHair 不想让自己纠结，所以请你计算出直到所有猫猫都被拿出房间时，AzureHair 的最小纠结次数是多少。
输入格式
本题有多组测试数据。
第一行一个整数 T。
接下来 T 行，每行一个整数 n。
输出格式
T 行，每行一个整数表示最小纠结次数。
输入输出样例
输入 #1复制
2 13 7
输出 #1复制
3 2
说明/提示
【样例解释】
对于 13 只猫猫，只纠结 3 次的过程如下：
选择交出 7 只猫猫，剩余 6 只；
不纠结，交出 3 只猫猫，剩余 3 只；
选择交出 2 只猫猫，剩余 1 只；
选择交出 1 只猫猫，所有猫猫均被取走。
容易证明不存在少于 3 次纠结的方案。
【数据范围】
对于 10% 的数据，保证 1≤n≤10。
对于 30% 的数据，保证 1≤n≤10^5。
对于 100% 的数据，保证 1≤n≤2^60，1≤T≤5×10^5。
思路：
考虑dfs搜索。
#include<bits/stdc++.h>
using namespace std;
int n,s,ans;
void dfs(int num,int step){
if(num==0){
ans=min(step,ans);
return;
}
else if(num==1){
ans=min(step+1,ans);
return;
}
else if(num%2==0)dfs(num/2,step);
else{
dfs((num+1)/2,step+1);
dfs((num-1)/2,step+1);
}
}
int main(){
cin>>n;
while(n--){
ans=10000;
cin>>s;
dfs(s,0);
cout<<ans<<"\n";
}
}结果30pts，其他都TLE了。
考虑动态规划。
#include<bits/stdc++.h>
using namespace std;
const int mod=1000;
long long n,s,ans,f[mod];
int main(){
cin>>n;
while(n--){
cin>>s;
f[0]=0;
f[1]=1;
for(int j=2;j<=s;j++){
if(j%2==0)f[j%mod]=f[j/2%mod];
else f[j%mod]=min(f[(j+1)/2%mod],f[(j-1)/2%mod])+1;
}
cout<<f[s%mod]<<"\n";
}
}还是TLE了
考虑正解。
正解：
如果是奇数，纠结次数+1，
还如果减一除以二为奇数，则n+1
n/=2
Code:
#include<bits/stdc++.h>
using namespace std;
long long t,n,ans;
int main(){
cin>>t;
while(t--){
cin>>n;
ans=0;
while(n){
if(n&1){
ans++;
if(n&2)n++;
}
n>>=1;
}
cout<<ans<<"\n";
}
}