A.Bits(CodeforcesRound#276(div1)_html/css_WEB-ITnose
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了A.Bits(CodeforcesRound#276(div1)_html/css_WEB-ITnose,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2621字,纯文字阅读大概需要4分钟。
内容图文
![A.Bits(CodeforcesRound#276(div1)_html/css_WEB-ITnose](/upload/InfoBanner/zyjiaocheng/400/34c21bf22dec4e919d4421fbf0ce36a8.jpg)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Let's denote as the number of bits set ('1' bits) in the binary representation of the non-negative integer x.
You are given multiple queries consisting of pairs of integers l and r. For each query, find the x, such that l?≤?x?≤?r, and is maximum possible. If there are multiple such numbers find the smallest of them.
Input
The first line contains integer n ? the number of queries (1?≤?n?≤?10000).
Each of the following n lines contain two integers li,?ri ? the arguments for the corresponding query (0?≤?li?≤?ri?≤?1018).
Output
For each query print the answer in a separate line.
Sample test(s)
input
31 22 41 10
output
137
Note
The binary representations of numbers from 1 to 10 are listed below:
110?=?12
210?=?102
310?=?112
410?=?1002
510?=?1012
610?=?1102
710?=?1112
810?=?10002
910?=?10012
1010?=?10102
第1次打div1,就赶上cf挂了,不算rating,在25分钟交了一发,判了半个多小时,最后返回个RE,竟然位运算爆int了,过了A题就睡觉去了
给出一段区间的左端点和右端点,求这段区间的二进制的1最多的最小的。
先把左区间L化为二进制,再把左区间的二进制的从最小位开始,每位变为1,因为这是在当前1的个数中最小的且大于L的。直到大于右区间R。
代码:
#include#include #include #include using namespace std;long long a[100];int main(){ long long l,r; int n; scanf("%d",&n); while(n--) { scanf("%I64d%I64d",&l,&r); memset(a,0,sizeof(a)); int cou=0; long long ans=l; while(l>0) { a[cou++]=(l%2); l=l/2; } for(int i=0;; i++) { a[i]=1; long long temp=0; for(int j=0; j<max(cou,i+1); j++) { temp+=(a[j]<<j); } if(temp<=r) ans=temp; else break; } printf("%I64d\n",ans); } return 0;}
内容总结
以上是互联网集市为您收集整理的A.Bits(CodeforcesRound#276(div1)_html/css_WEB-ITnose全部内容,希望文章能够帮你解决A.Bits(CodeforcesRound#276(div1)_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。