蓝桥杯刷题冲刺 | 倒计时6天

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

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

文章目录

  • 1.凑数
  • 2.砝码称重

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≤ 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;
    }
    
  • 反思

    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^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 二选一,运气好的话,拿一半多得分

Alt

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/6354.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CesiumForUnreal实现贴地面(SurfacePolygon)效果

文章目录 1.实现目标2.实现过程2.1 材质实例2.2 Cartographic Polygon2.3 Runtime环境使用2.4 效果测试2.5 遇到的UE崩溃问题与解决3.参考资料1.实现目标 基于UE5的Cesium-Unreal插件添加在线世界地形Cesium World Terrain,在地形表面绘制Polygon面,并使其紧贴地形,实现贴地…

实验四 配置OSPF协议

目录 一、实验内容 二、实验环境 三、实验步骤 一、实验内容 在配置NAT实验的基础上&#xff0c;增加R0到R1的GRE VPN隧道&#xff0c;并将10.0.0.0/24网络和192.168.0.0/24网络通过GRE隧道192.168.2.0/24网络连通&#xff0c;使用OSPF协议路由&#xff0c;使得PC2能访问PC0…

MongoDB - 索引知识

索引简介 什么是索引 索引最常用的比喻就是书籍的目录&#xff0c;查询索引就像查询一本书的目录。 索引支持 MongoDB 查询的高效执行。如果没有索引&#xff0c;MongoDB 必须扫描集合中每一个文档&#xff0c;以选择与查询语句相匹配的文档。如果查询存在适当的索引&#x…

深入学习JavaScript系列(七)——Promise async/await generator

本篇属于本系列第七篇 第一篇&#xff1a;#深入学习JavaScript系列&#xff08;一&#xff09;—— ES6中的JS执行上下文 第二篇&#xff1a;# 深入学习JavaScript系列&#xff08;二&#xff09;——作用域和作用域链 第三篇&#xff1a;# 深入学习JavaScript系列&#xff…

ChatGPT探索系列之二:学习GPT模型系列的发展历程和原理

文章目录前言一、GPT的起源GPT系列二、GPT的原理1. GPT原理&#xff1a;自注意2. GPT原理&#xff1a;位置编码3. GPT原理&#xff1a;Masked Language Modeling4. GPT原理&#xff1a;预训练5. GPT原理&#xff1a;微调6. GPT原理&#xff1a;多任务学习三、GPT模型的风险与挑…

二叉搜索树BST的学习

文章目录二叉搜索树BST什么是BST&#xff1f;用BST做什么&#xff1f;一、BST的特性BST的特性是什么&#xff1f;1.[230. 二叉搜索树中第K小的元素](https://leetcode.cn/problems/kth-smallest-element-in-a-bst/)2.[538. 把二叉搜索树转换为累加树](https://leetcode.cn/prob…

Git Commit Message 应该怎么写?

原文链接&#xff1a; Git Commit Message 应该怎么写&#xff1f; 最近被同事吐槽了&#xff0c;说我代码提交说明写的太差。其实都不用他吐槽&#xff0c;我自己心里也非常清楚。毕竟很多时候犯懒&#xff0c;都是直接一个 -m "fix" 就提交上去了。 这样做是非常…

C语言变量

C 变量 变量其实只不过是程序可操作的存储区的名称。C 中每个变量都有特定的类型&#xff0c;类型决定了变量存储的大小和布局&#xff0c;该范围内的值都可以存储在内存中&#xff0c;运算符可应用于变量上。 变量的名称可以由字母、数字和下划线字符组成。它必须以字母或下…

机器学习-卷积神经网络CNN中的单通道和多通道图片差异

背景 最近在使用CNN的场景中&#xff0c;既有单通道的图片输入需求&#xff0c;也有多通道的图片输入需求&#xff0c;因此又整理回顾了一下单通道或者多通道卷积的差别&#xff0c;这里记录一下探索过程。 结论 直接给出结论&#xff0c;单通道图片和多通道图片在经历了第一…

【hello C语言】结构体(下)

目录 1.结构体的声明 1.1 结构的声明 1.2 特殊声明&#xff1a;匿名结构体 1.3 结构的自引用 2. 结构体的定义和初始化 3. 结构体的内存对齐 3.1 内存对齐规则 3.2 内存对齐存在的原因 3.3 修改默认对其数 4. 结构体传参 C语言&#x1f6f4; 1.结构体的声明 结构体便是描述复杂…

一种适合容器化部署的雪花算法ID生成器

雪花算法简介 SnowFlake 中文意思为雪花&#xff0c;故称为雪花算法。最早是 Twitter 公司在其内部用于分布式环境下生成唯一 ID。 雪花算法有以下几个优点&#xff1a; 高并发分布式环境下生成不重复 id&#xff0c;每秒可生成百万个不重复 id。基于时间戳&#xff0c;以及同…

零编程经验,通过 GPT-4 十分钟开发了一个浏览器插件,并成功运行,实现了需求目标!

大佬蓝鸟ID: sundyme零编程经验&#xff0c;通过 GPT-4 十分钟开发了一个浏览器插件&#xff0c;并成功运行&#xff0c;实现了需求目标&#xff01;太不可思意了&#xff0c;真正体会到了自然语言编程的魅力&#xff01; 下一步是利用Pinterest 的 API 接口实现自动发图&#…

No.026<软考>《(高项)备考大全》【第10章】项目沟通和干系人管理(第2部分-干系人管理)

1 干系人管理部分相关 1.1 干系人ITO 1.2 干系人管理 过程过程的定义过程的作用识别干系人识别能影响项目决策、活动或结果的个人、群体或组织&#xff0c;以及被项目决策、活动或者结果影响的个人、群体或者组织&#xff0c;并分析和记录他们的相关信息的过程帮助项目经理建…

此战成硕,我成功上岸西南交通大学了~~~

友友们&#xff0c;好久不见&#xff0c;很长时间没有更一个正式点的文章了&#xff01; 是因为我在去年年底忙着准备初试&#xff0c;今年年初在准备复试&#xff0c;直到3月底拟录取后&#xff0c;终于可以写下这篇上岸贴&#xff0c;和大家分享一下考研至上岸的一个过程 文章…

游戏算法-游戏AI行为树,python实现

参考文章&#xff1a;Behavior trees for AI: How they work (gamedeveloper.com) 本文主要参考上述weizProject Zomboid 的开发者 Chris Simpson文章的概念&#xff0c;用伪代码实现代码例子 AI概述 游戏AI是对游戏内所有非玩家控制角色的行为进行研究和设计&#xff0c;使得游…

电子拣货标签9代系统简介

CK_Label_v9一、产品参数 产品型号 CK_Label_v9 LED 3&#xff08;红&黄&绿&#xff09;独立可控 供电方式 DC 24V 0.2A 通信方式 无线通信 蜂鸣器 支持 尺寸 D60 H307mm 二、革新点 配合标签拣货使用三个灯&#xff08;红黄绿&#xff09;都可以被独立控…

基于MATALB编程的BP神经网络手臂血管分类识别,基于BP神经网络的图像分类

目标 背影 BP神经网络的原理 BP神经网络的定义 BP神经网络的基本结构 BP神经网络的神经元 BP神经网络的激活函数&#xff0c; BP神经网络的传递函数 数据 神经网络参数 基于BP神经网络手臂血管识别的MATLAB代码 效果图 结果分析 展望 背影 随着人工智能的发展&#xff0c;智…

贪心算法-删数问题C++

目录 一、题目 二&#xff1a;思路 代码 运行结果 一、题目 有一个长度为n&#xff08;n < 240&#xff09;的正整数&#xff0c;从中取出k&#xff08;k < n&#xff09;个数&#xff0c;使剩余的数保持原来的次序不变&#xff0c;求这个正整数经过删数之后最小是多…

用Python绘制六种可视化图表,简直太好用了

前言 嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python资料、源码、教程: 点击此处跳转文末名片获取 可视化图表&#xff0c;有相当多种&#xff0c;但常见的也就下面几种&#xff0c;其他比较复杂一点&#xff0c;大都也是基于如下几种进行组合&#xff0c;变换出来的。 …

记录--CSS 如何实现羽化效果?

这里给大家分享我在网上总结出来的一些知识&#xff0c;希望对大家有所帮助 最近碰到这样一个问题&#xff0c;在一张封面上直接显示书名&#xff0c;可能会存在书名看不太清楚的情况(容易受到背景干扰)&#xff0c;如下 为了解决这个问题&#xff0c;设计师提了一个“究极”方…
最新文章