题解：P10892 SDOI2024
Frank_G
·
·
题解
题目传送门
大致题意
每次询问输入一个整数 $n$，对于这个整数 $n$ 进行如下操作直到 $n = 0$：
**当 $n$ 为奇数时**：AzureHair 会纠结减去 $\frac{n-1}{2}$ 或 $\frac{n+1}{2}$。
**当 $n$ 为偶数时**：AzureHair 会直接减去 $\frac{n}{2}$。
求 AzureHair **最小**的纠结次数。
# 做法思路
相信大家看到这道题就已经想到了这是一道与二进制相关的题目，那么它究竟该如何处理呢？
## Step 1
既然我们要用二进制的思路解决此问题，那么我们需要一个数组 $a$ 来存储。
其核心代码为：
```cpp
memset(a,0,sizeof(a));
int flag=0;
while(n){
flag++;
a[flag]=n%2;
n/=2;
}
```
## Step 2
之后我们需要遍历 $n$ 在二进制下的每一位，此处我们需要进行分类讨论（假设遍历至第 $i$ 位）：
### 1、当 $a_{i}=0$ 时
可以不进行任何考虑，直接遍历下一位就好了。
### 2、当 $a_{i}=1$ 时
此时又要分两种情况：
#### (1)当 $a_{i+1}=0$ 时
若选择在第 $i$ 位 $-1$，则第 $i+1$ 位就不需要再纠结了；但如果选择在第 $i$ 位 $+1$，则第 $i+1$ 位仍需要纠结。显然前者是更优的。
#### (2)当 $a_{i+1}=1$ 时
若在第 $i$ 位选择 $-1$，则第 $i+1$ 位仍需要纠结。但如果选择在第 $i$ 位 $+1$，从第 $i$ 位开始的连续的值为 $1$ 的位置都不需要纠结了。显然后者是更优的。
这一部分的核心代码为（由于作者习惯问题，在这段代码之前将数组 $a$ 进行了倒序）：
```cpp
for(int i=1;i<=flag;i++){
if(a[i]==0) continue;
else{
if(a[i+1]==0) ans++;
else{
ans++;
for(int j=i;j<=flag+1;j++){
if(a[j]==1) a[j]=0;
else{
a[j]=1;
break;
}
}
}
}
}
```
## Step 3
解决完之后我们需要处理一个小细节，就是当操作完 Step 2 后，第 $flag+1$ 位可能会变成 $1$，因此我们需要进行特判。
其核心代码为：
```cpp
if(a[flag+1]==1) ans++;
```
# 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
int t;
int a[70],ans;
int main()
{
cin >> t;
while(t--){
cin >> n;
ans=0;
memset(a,0,sizeof(a));
int flag=0;
while(n){
flag++;
a[flag]=n%2;
n/=2;
}
for(int i=1;i<=flag;i++) swap(a[i],a[flag-i+1]);
for(int i=1;i<=flag;i++){
if(a[i]==0) continue;
else{
if(a[i+1]==0) ans++;
else{
ans++;
for(int j=i;j<=flag+1;j++){
if(a[j]==1) a[j]=0;
else{
a[j]=1;
break;
}
}
}
}
}
if(a[flag+1]==1) ans++;
cout << ans << endl;
}
return 0;
}
```
然后你就可以像我一样 AC 啦。
**声明+提醒：一定要自己写一遍，否则你不知道你有哪里还没明白！！！**