首页 > 代码库 > CodeForces484A——Bits(贪心算法)
CodeForces484A——Bits(贪心算法)
Bits
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
3
1 2
2 4
1 10
Output
1
3
7
题目大意：
给定L，R，输出X，X为[L,R]中化为二进制之后一的个数最多的那个数，（同时存在多个解，输出最小的那个）。
解题思路：
设L，R的从高位开始有t1位相同，那么根据常识，x的前t1位（从高位开始数）必然也与LR相同。又因为L<=R,那么t1+1位不同，必然是L为0，R为1。
此时将x的t1+1位赋值为0，后面所有为都为1。那么求出的X： L<=x<R 成立，且在[L,R)区间中为最优解。
存在特殊情况：R换成二进制之后全部为1，所以要加一个判断。判断x在t1+1位为1的时候是否绝对大于R，绝对大于的话，就将t1+1赋值为0;反之，赋值为1。
Code:
1 /************************************************************************* 2 > File Name: CF484A.cpp 3 > Author: Enumz 4 > Mail: 369372123@qq.com 5 > Created Time: 2014年11月06日 星期四 01时49分25秒 6 ************************************************************************/ 7 8 #include<iostream> 9 #include<cstdio>10 #include<cstdlib>11 #include<string>12 #include<cstring>13 #include<list>14 #include<queue>15 #include<stack>16 #include<map>17 #include<set>18 #include<algorithm>19 #include<cmath>20 #include<bitset>21 #include<climits>22 #define MAXN 10000023 #define LL long long24 using namespace std;25 int main()26 {27 LL a,b,ans;28 int T,k;29 cin>>T;30 while (T--)31 {32 ans=0;33 cin>>a>>b;34 int i;35 bool flag=0;36 for (i=60; i>=0; i--)37 {38 if (flag)39 {40 ans+=1LL<<i;41 continue;42 }43 if((a&(1LL<<i))==(b&(1LL<<i)))44 {45 if ((a&(1LL<<i))!=0)46 ans+=1LL<<i;47 }48 else49 {50 flag=1;51 k=i;52 i++;53 }54 }55 if (ans>b)56 ans=ans^(1LL<<k);57 cout<<ans<<endl;58 }59 return 0;60 }
CodeForces484A——Bits(贪心算法)