5146: 最强单身狗

题目描述

有若干只单身狗排成一排，编号从 l 到 r。GBX 发现，一个单身狗的编号的二进制中 1 的数量越多，表示该单身狗越强(就是单身越久咯 -_-|||)。GBX 想找到一只最强的单身狗和他做朋友(强者惺惺相惜吧 >_<)。

输入

输入一个 T（T ≤ 1000）表示 T 组数据。

输出

对于每组数据输入两个正整数

l，r（1 ≤ l ≤ r ≤ 1018 ），表示单身狗的标号。

对于每组数据输出一个数表示最强的单身狗的标号(如果有多个输出最小的那个)，每组数据占一行。

样例输入

2

1 100

123 654

样例输出

63

511

这道题如果用到一个C语言里面的知识就会简单很多，“|”这个玩意儿，很多人可能想不起来了（我当然，也是，嘿嘿，看了提示之后才知道的）

“|” ：按位OR，就是数学里面的求并集

比如， 4|9    =>  0010  |  1001(将其转化为二进制)   => 1011(同位置上，只要有1，则结果位置上为1；反之，两人同位置上都是0，则结果位置为0；)  

结果答案    4|9 = 11（将结果二进制 自动 转化为十进制）

题目分析：从a到b标号，就是一个闭区间 [a,b]，将此区间的数字（十进制）转化为二进制时，二进制中含“1”最多的那个标号，就是最终答案；假如有重复的，选择标号最小的那个

标号最小，意味着“1”的位数越低越好。 假如，左值 a|a+1 （其中1都合并了）的值（十进制）比右值b要小，就一直向右移动；比右值b大，循环结束，a就是最终答案（a在代码中值会变）

a|a+1 得到的值 一定在原区间内   随着“1”合并的越来越多，退出循环时的那个标号，就是最强“狗子”

AC代码  

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long int a,b; //这道题数据很大，用LL或__int64都可以 
        cin>>a>>b;
        while((a|a+1)<b)
          a=(a|a+1);
         cout<<a<<endl;
    }
}      

转载于:https://www.cnblogs.com/lenka-lyw/p/10912423.html