备战蓝桥杯----贪心算法(二进制)

已经差不多掌握了贪心的基本思想,让我们看几道比较趣的题吧!

先来个比较有意思的题热热身:

法1.我们可以先把l,r化成二进制的形式。

然后分俩种情况:

(1)若他们位数不一样并且位数高的全为1,那么答案即位数高的数

(2)若他们位数不一样并且位数高的不全为1,那么可以构造011111这样的数

(3)若他们位数一样,那么从左往右,前面照抄直到遇到两个不一样的位数,后面方法同上

法2.我们可以先把l化成二进制的形式。

然后从低位到高位,遇到0就变1,在判断是否超出了r.

因为从低位到高位,所以在相同1的个数的条件下,这样的增幅是最小的。

那么我们来个题:

这题还是比较容易,我们只要用前缀和把每个数的某一位的01个数统计出来,如果0多,那么x的那一位就取1;

下面为AC代码:

再来一题类似的:

很显然,我们先把L,R转为二进制,然后从高位开始到第一个位数不同的地方,然后让为1的位后面跟上00000.....,然后让为0的位后面跟上11111....,即可。下面是AC代码:

让我们看一道比较难的题目吧

下面是分析:

首先,我们按位进行贪心,使每一位经过运算后变为1;

那如何快速的知道某一位是1还是0经过运算后变为1呢?

我们可以分别用11111串与000000串去运算再比较结果即可。

下面是AC代码:

相关推荐

  1. 备战Day28 - 贪心算法

    2024-01-29 23:24:02       18 阅读
  2. 备战Day29 - 贪心-活动选择问题

    2024-01-29 23:24:02       22 阅读
  3. 贪心+

    2024-01-29 23:24:02       45 阅读
  4. 二进制王国【算法双周赛】

    2024-01-29 23:24:02       20 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-01-29 23:24:02       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-01-29 23:24:02       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-01-29 23:24:02       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-01-29 23:24:02       20 阅读

热门阅读

  1. C#学习笔记_关键字ref、out

    2024-01-29 23:24:02       33 阅读
  2. leetCode 第十五天

    2024-01-29 23:24:02       39 阅读
  3. 聊聊 FTP、SFTP、FTPS

    2024-01-29 23:24:02       33 阅读
  4. 个人关于背包问题的·总结(三)

    2024-01-29 23:24:02       30 阅读
  5. git修改用户名与邮箱

    2024-01-29 23:24:02       41 阅读
  6. MySQL数据库免费客户端简介

    2024-01-29 23:24:02       36 阅读
  7. LeetCode 53 最大子数组和

    2024-01-29 23:24:02       39 阅读
  8. 实用SQL语句(postgres)

    2024-01-29 23:24:02       38 阅读