题解 | #造数#

A题：

题目： 给定一个整数 n ，你可以进行以下三种操作

操作1：+1

操作2；+2

操作3：×2

问最少需要多少次操作可以将 0 转为为n。

其实就是在问你怎么用这三种操作构造出任意一个数。 假设第i次操作后，得到的数为ai，

那么下一个数a(i+1)可以是2*ai,ai+1,ai+2;

a0=0为偶数，操作2，3不会改变其奇偶性，所以奇数一开始只能由操作1获得。

偶数可以由操作2，3获得，但是操作3增加得更快，所以为偶数时先考虑是不是由操作3得来的，即操作3只能由偶数相乘得到。

余下情况的就是操作2了。

#include<iostream>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double llf;


ll OpGet(ll n){
	if(n==0) return 0;
	if(n==1) return 1;
	if(n==1) return 1;
	if((n&1)==0){
		if(n%4==0){
			return OpGet(n/2)+1;
		}else{
			return OpGet(n-2)+1;
		}
		
	}else{
		return OpGet(n-1)+1;
	}
}
void solve() {
	ll x;cin>>x;
	cout<<OpGet(x)<<endl;
}


int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
	while(t--){
		solve();
	}
	return 0;
}