题目:让你求从x到y中(1<=x<=y<=10^18),二进制一的个数最多的数是哪个,如果有多个相同的答案,输出最小的。

题目链接:https://www.nitacm.com/problem_show.php?pid=20317

类似题目及题解:https://www.cnblogs.com/myrtle/p/11662171.html

分析:先把x和y转换成二进制位:

(假设x,y最高位不是同一位):则答案可以取11111

(如果LR最高位相同):则最高位的数一定取,然后比较减去最高位后,剩下的数

特判:y的二进制全是1时,答案为y。

注意:&运算优先级低于==,需要加括号

#include<bits/stdc++.h>
using namespace std;
int cal2(long long n)//计算二进制有几个1
{
int cnt=;
for(int i=;i>=;i--)
{
long long tmp=1ll<<i;
if(n>=tmp)n-=tmp,cnt++;
}
return cnt;
} long long cal(long long x,long long y)
{
for(int i=;i>=;i--)
{
long long tmp=1ll<<i;
if((tmp&y)==tmp)//最高位
{
if((tmp&x)==(tmp&y))//最高位相等
{
return tmp+cal(x-tmp,y-tmp);
}
else//最高位不相等
{
long long ans=;
for(int j=i-;j>=;j--)
{
ans+=(1ll<<j);
}
return ans;
}
}
}
return ;
}
int main()
{
int T;
long long x,y;
cin>>T;
while(T--)
{
cin>>x>>y;
long long ans=cal(x,y);
if(cal2(y)>cal2(ans))ans=y;
cout<<ans<<endl;
}
return ;
}

最新文章

  1. 迭代器 iterator(二): 用iterator遍历arraylist
  2. Delphi组件indy 10中IdTCPServer修正及SSL使用心得
  3. Regex.Escape
  4. Permutations 解答
  5. iOS更新之DFU模式和恢复模式
  6. 解决 configure.ac:17: error: possibly undefined macro: AC_PROG_LIBTOOL
  7. WebPack介绍
  8. numpy数组扩展函数repeat和tile用法
  9. SpringMVC中的一些注解
  10. Linux下安装JDK7和TomCat7
  11. Bootstrap 标签页(Tab)插件
  12. unity3d动态创建一个文本
  13. IDE MAC下的快捷键,自定义代码块。
  14. 为什么不要在Spring的配置里,配置上XSD的版本号
  15. 关于CreateProcess函数一些经验
  16. 陈新宇:CKafka在人脸识别PAAS中的应用
  17. Codeforces Round #247 (Div. 2) ABC
  18. C语言字符串的输入输出
  19. ubuntu eclipse opencv环境配置
  20. Linux-shell实现阳历转农历(序)

热门文章

  1. php windows与linux下的路径区别
  2. Python面向对象 | 静态方法 staticmethod
  3. TRANK和VTP
  4. 网站搭建-2-本地网站搭建-安装Linux虚拟机/ 安装IIS Windows
  5. 点击a标签的时候出现虚影
  6. C++对象模型结论
  7. 人人都懂区块链--pdf电子版学习资料下载
  8. nyoj 517-最小公倍数 (python range(start, end) range(length))
  9. zabbix 发送报警邮件
  10. 【Stream—7】NetworkStream相关知识分享