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