备战蓝桥杯----贪心算法（二进制）
已经差不多掌握了贪心的基本思想，让我们看几道比较趣的题吧！
先来个比较有意思的题热热身：
法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代码：
原文地址：https://blog.csdn.net/cocoack/article/details/135785206
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！