CodeForces 484A Bits - c++编程基础

题意：

10000个询问每个询问输入L和R（10^18）输出在区间内二进制表示下1最多的数字如果1个数相同输出最小的

思路：

YY一下觉得后几位全是1的时候能保证1的个数多那么如何构造出这个数字呢？？

将L和R都变成二进制从高位到低位 L和R相同的那几位一定是不变的因为要保证构造出的数字在区间内然后分两种情况

一是L和R一直相同那就没什么好说的了就是它了

二是发现了有一位不同这时R的那个位一定是1 L的一定是0 那么只要把R的那个1变成0 然后把后面的所有位都变成1就构造出了数字这时一定1最多吗？？不一定比如 R=101111 L=100000 构造出来是100111 这时要特判一下如果把差异的那一位变回1是不是超过R 不超过的话变回来更优

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               using namespace std; typedef long long LL; int main() { int n; LL l, r, ans; scanf("%d", &n); while (n--) { cin >> l >> r; ans = 0; for (int i = 61; i >= 0; i--) { if ((r & (1LL << i)) && !(l & (1LL << i))) { ans |= (1LL << i); ans--; if (ans + (1LL << i) <= r) ans += (1LL << i); break; } else { if (r & (1LL << i)) ans |= (1LL << i); } } cout << ans << endl; } return 0; }