nitacm20317 来自张司机的挑战书
2024-09-01 21:05:29
题目:让你求从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 ;
}
最新文章
- 迭代器 iterator(二): 用iterator遍历arraylist
- Delphi组件indy 10中IdTCPServer修正及SSL使用心得
- Regex.Escape
- Permutations 解答
- iOS更新之DFU模式和恢复模式
- 解决 configure.ac:17: error: possibly undefined macro: AC_PROG_LIBTOOL
- WebPack介绍
- numpy数组扩展函数repeat和tile用法
- SpringMVC中的一些注解
- Linux下安装JDK7和TomCat7
- Bootstrap 标签页(Tab)插件
- unity3d动态创建一个文本
- IDE MAC下的快捷键,自定义代码块。
- 为什么不要在Spring的配置里,配置上XSD的版本号
- 关于CreateProcess函数一些经验
- 陈新宇:CKafka在人脸识别PAAS中的应用
- Codeforces Round #247 (Div. 2) ABC
- C语言字符串的输入输出
- ubuntu eclipse opencv环境配置
- Linux-shell实现阳历转农历(序)
热门文章
- php windows与linux下的路径区别
- Python面向对象 | 静态方法 staticmethod
- TRANK和VTP
- 网站搭建-2-本地网站搭建-安装Linux虚拟机/ 安装IIS Windows
- 点击a标签的时候出现虚影
- C++对象模型结论
- 人人都懂区块链--pdf电子版学习资料下载
- nyoj 517-最小公倍数 (python range(start, end) range(length))
- zabbix 发送报警邮件
- 【Stream—7】NetworkStream相关知识分享