????马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦????
1.凑数
-
题目
初始时，n=0。
每一轮操作都要依次完成两个步骤：
- 第一步，任选一个非负整数 a，将 n 增加 a，这一步所需付出的代价为 a。
- 第二步，将 n 乘以 2，这一步无需付出任何代价。
你可以不断重复上述操作。
给定一个整数 x，你的任务是使 n 在某一步操作后（不一定是某一轮结束后）恰好等于 x 且付出的总代价尽可能少。
请你计算，为了完成任务所需付出的最小总代价。
例如，如果 x=5，则最佳操作方案为：
- 第 1 轮操作中，第一步，将 n 增加 1（付出代价 1），使得 n 变为 1，第二步，将 n 乘以 2，使得 n 变为 2。
- 第 2 轮操作中，第一步，将 n 增加 0（付出代价 0），则 n 仍然为 2，第二步，将 n 乘以 2，使得 n 变为 4。
- 第 3 轮操作中，第一步，将 n 增加 1（付出代价 1），使得 n 变为 5。此时 n 等于 x 成立，任务完成。
- 付出的最小总代价为 2。
再例如，如果 x=8，则最佳操作方案为：
- 第 1 轮操作中，第一步，将 n 增加 1（付出代价 1），使得 n 变为 1，第二步，将 n 乘以 2，使得 n 变为 2。
- 第 2 轮操作中，第一步，将 n 增加 0（付出代价 0），则 n 仍然为 2，第二步，将 n 乘以 2，使得 n 变为 4。
- 第 3 轮操作中，第一步，将 n 增加 0（付出代价 0），则 n 仍然为 4，第二步，将 n 乘以 2，使得 n 变为 8。此时 n 等于 x 成立，任务完成。
- 付出的最小总代价为 1。
输入格式
一个整数 x。
输出格式
一个整数，表示所需付出的最小总代价。
数据范围
前 3 个测试点满足 1≤x≤10。
所有测试点满足 1≤x≤ 1 0 9 10^9 109 。输入样例1：
5输出样例1：
2输入样例2：
8输出样例2：
1 -
第一次 AC 4/10
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; if(n%2==0||n==1) cout<<1; else cout<<2; return 0; } -
题解1 转换思路，倒推，偶数没有代价，奇数的代价+1
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int ans=0; while(n) { ans+=n%2; n/=2; //偶数没有代价，奇数代价+1 } cout<<ans; return 0; } -
题解2 模拟二进制，计算二进制中1出现的次数
step1: (n+a1)*2
step2: ((n+a1)* 2+a2)* 2
step3: (((n+a1)* 2+a2)* 2+a3)*2
ans=a1+a2+a3
发现t应该是多个2的多次幂的相加，马上就能联想到二进制，而答案就是a1 + a2 + … + an，而且二进制每个位是0/1，所以只需要统计1的数量即可
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int ans=0; while(n) { ans++; n&=(n-1); //这里是计算 n 二进制中1的个数 } //执行一次x = x&(x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0 cout<<ans; return 0; } -
反思
- 第一次，直接不断地乘2，错以为每个偶数都可以包含在内，4*2=8，6就没有包含进去；
- 题解转换思维，从后往前推，这样结果 x 一定包含在内，此过程中偶数没有代价，奇数代价+1；
- 模拟二进制，计算一个数二进制中 1 的个数，又学到了
while(n) { ans++; n&=(n-1); //这里是计算 n 二进制中1的个数 }
2.砝码称重
-
题目
给定一个天平和 101 个砝码。
101 个砝码的重量依次为 n 0 , n 1 , n 2 , … , n 100 n^0,n^1,n^2,…,n^{100} n0,n1,n2,…,n100 克，其中 n 是一个不小于 2 的整数。
请你判断，我们能否利用给定天平和砝码对重量为 m 克的物品进行称重。
注意，天平的两端都可以放入砝码。
具体来说，你的任务是判断是否可以在天平的左盘放入重量为 m 克的物品以及一些砝码（也可以不放砝码），并在天平的右盘放入一些砝码，从而使得天平的两端可以保持平衡。
不要求用到所有砝码，挑选合适的砝码使用即可。
例如，如果 n=3,m=7，则我们可以在天平的左盘放入重量为 7 克的物品以及重量为 3 克的砝码，并在天平的右盘放入重量为 1,9 克的砝码，这样可以使得天平两端保持平衡。
输入格式
共一行，包含两个整数 n,m。
输出格式
如果可以对重量为 m 克的物品进行称重，则输出
YES，否则输出NO。数据范围
前 5 个测试点满足 2≤n≤100，1≤m≤100。
所有测试点满足 2≤n≤ 1 0 9 10^9 109，1≤m≤ 1 0 9 10^9 109 。输入样例1：
3 7输出样例1：
YES输入样例2：
100 99输出样例2：
YES输入样例3：
100 50输出样例3：
NO -
第一次 AC 8/21
#include<bits/stdc++.h> using namespace std; int main() { int n,m; cin>>n>>m; for(int i=0;i<101;i++) for(int j=0;j<=i;j++) { if(pow(n,i)-pow(n,j)==m||pow(n,i)==m) //这里考虑的太简单，天平的一个盘子上既可以放物品，也可以放砝码，我忽略掉 { puts("YES"); return 0; } } puts("NO"); return 0; } -
骗分——新方法 AC 17/21
#include<bits/stdc++.h> using namespace std; int main() { int n,m; cin>>n>>m; puts("YES"); return 0; } //满意 -
题解
假设存在m使得等式成立那么一定有
m + n的k1 + n的k2 + n的k3 + … = n的k4 + n的k5 + …如果k都不是0的话，将m移到等式的一边，另一边都是n的k次幂相加，那么m一定可以被n整除。 设为条件1
但是k是可以为0的，所以可能等式两边存在1， 那么m等于n的k次幂相加再 + 1 或 -1 ，那么对m进行+1或-1可以让他继续满足条件1，如此循环，如果m + 1 或 -1都无法满足条件1。说明m无法凑成多个n的k次幂相加减，等式无法成立，就无解。
否则操作到最后，m会变成n的0次= 1。思路就是：如条件1满足，我们就等式两边除以n。 如果出现了n的0次幂，就+1或-1消去，此时的m还是满足条件的。
如果条件1不满足，而且对m + 1 或 -1 都无法满足条件1， 那么m就无法被n的不同次幂的砝码在等式中拼凑
出来。#include<bits/stdc++.h> using namespace std; int m, n; int main() { cin >> n >> m; while(m > 1) { // cout << m << endl; if(m % n == 0) m /= n; else if((m + 1) % n == 0) m++; else if((m - 1) % n == 0) m--; else { cout << "NO"; return 0; } } cout << "YES"; return 0; } -
反思
学到新技能——骗分，yes or no 二选一，运气好的话，拿一半多得分
