蓝桥杯刷题冲刺 | 倒计时6天-Toy模板网

这篇具有很好参考价值的文章主要介绍了蓝桥杯刷题冲刺 | 倒计时6天。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

1.凑数

题目

链接： 4941. 凑数 - AcWing题库
初始时，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≤ $10^9$ 。

输入样例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;
}

反思
1. 第一次，直接不断地乘2，错以为每个偶数都可以包含在内，4*2=8，6就没有包含进去；
2. 题解转换思维，从后往前推，这样结果 x 一定包含在内，此过程中偶数没有代价，奇数代价+1；
3. 模拟二进制，计算一个数二进制中 1 的个数，又学到了
```
 while(n)
    {
        ans++;
        n&=(n-1);  //这里是计算 n 二进制中1的个数
    } 
```

2.砝码称重

题目

链接： 4942. 砝码称重 - AcWing题库
给定一个天平和 101 个砝码。

101 个砝码的重量依次为 $n^0,n^1,n^2,…,n^{100}$ 克，其中 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≤ $10^9$ ，1≤m≤ $10^9$ 。

输入样例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 二选一，运气好的话，拿一半多得分