D - Bits

题目链接：https://vjudge.net/contest/207454#problem/D

题目大意：给n组数据，每组包括l，r，找数x；

x满足条件：1.属于[l,r]。2.x的二进制数中包含的1最多且x最小。

数据范围：(1 ≤ n ≤ 10000).(0 ≤ l_i ≤ r_i ≤ 10¹⁸).

解题思路：贪心。。。首先根据数据范围，10^8，大概2^61.

先令二进制数每位都是1，然后从高位依次减掉1，使得答案在[l,r]之间。另外二进制每位均由1构成的数是二进制数中包含的1数量相同的数中最小的一个。

代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
long long f[65],a,b,ans;
int n;
int main()
{
    f[0]=1;
    for(int i=1;i<=61;++i) f[i]=f[i-1]*2; //构造10,100,1000,10000.。。。以便下面从高位减掉1.
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        ans=(1LL<<62)-1;//令二进制数每位都是1
        for(int i=62;i>=0;--i)
        {
            if(ans>b && ans-f[i]>=a) ans-=f[i];//ans>b且减掉最高位上1能>=a,则减
            if(ans>=a && ans<=b) break;找到符合条件数，退出循环
        }
        cout<<ans<<endl;
   }
   return 0;