毕业设计做视频网站设计,耒阳在那做网站,施工效果图怎么做,网站备案证书下载失败河南萌新联赛2024第#xff08;一#xff09;场#xff1a;河南农业大学 A题
造数
题目描述 样例 #1
样例输入 #1
2样例输出 #1
1样例 #2
样例输入 #2
5样例输出 #2
3做题思路
本题可以用逆推法 将三种操作反过来变为 − 1 , − 2 , / 2 -1 , -2 , /2 −1,−2,/2 …河南萌新联赛2024第一场河南农业大学 A题
造数
题目描述 样例 #1
样例输入 #1
2样例输出 #1
1样例 #2
样例输入 #2
5样例输出 #2
3做题思路
本题可以用逆推法 将三种操作反过来变为 − 1 , − 2 , / 2 -1 , -2 , /2 −1,−2,/2 问最少需要多少次可以将 n n n转化为 0 0 0
那么正常思维肯定是如果数字很大三个操作中 / 2 /2 /2是变小最快的。 直到到2了可以进行 − 2 -2 −2将其变为 0 0 0(不能看为 / 2 /2 /2,因为 0 ∗ 2 0 0*20 0∗20,而 0 2 2 022 022)
问题就在于偶数的乘除是可逆的但(在计算机整数运算中)奇数不是
具体的例子 7 / 2 3 7/2 3 7/23 , 但 3 ∗ 2 6 3*2 6 3∗26
所以逆推法在遇到奇数如果直接去除2最好推出的答案有问题。
最简单的例子就是 7 7 7 7 / 2 3 , 3 / 2 1 , 1 − 1 0 7/2 3 , 3/2 1 , 1-1 0 7/23,3/21,1−10为三部 但实际上三步无法从 0 0 0通过 1 , 2 , × 2 1,2,\times 2 1,2,×2变为 7 7 7
根本的原因就在于计算机整数运算的向下取整
所以最简单的解决办法就是遇到奇数通过加减将其变为偶数即可。
因为加减是可逆的无任何问题。
逆推法的在运用的重点在于每次操作必须可逆。 只需保证 n n n到 0 0 0的速度是最快的用的操作是最少的即可(其中暗含贪心思想)。 很容易验证除了 0 , 2 0,2 0,2以外的正偶数进行 / 2 /2 /2的操作一定是最佳的。 也就是说 a / 2 ≤ a − 2 a − 1 a/2 \le a-2 \lt a-1 a/2≤a−2a−1
对于奇数的证明从正推可以得到一点因为 2 2 2为偶数所以奇数只能通过 1 1 1操作得到。 也就对于着逆推的 − 1 -1 −1操作。
总结思路
从n开始遇到偶数就除二否则-1重复第二步直到数字变为2
答案就是操作第二步的步数1
时间复杂度分析
因为每次基本上都是以 / 2 /2 /2进行所以时间复杂度约为 O ( l o g 2 n ) O(log_2 n) O(log2n)
伪代码 赛时代码
#include iostream
#include queue
#include tuple
#include map
#define int long long
using namespace std;signed main(){int n;cin n;int sum 0;if(n1){sum ; n--;}while(n){if(n 2){sum ;break;}n 1;sum ;//cout n ;if(n1){sum ; n--;continue;}}cout sum;return 0;
}
