首页 > 代码库 > HDU 5969

HDU 5969

B君和G君聊天的时候想到了如下的问题。
给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。
其中|表示按位或,即C、 C++、 Java中的|运算。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<set>
#include<string>

using namespace std;

typedef long long LL;
int binary1[70],binary2[70];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL a,b;
        memset(binary1,0,sizeof(binary1));
        memset(binary2,0,sizeof(binary2));
        scanf("%lld%lld",&a,&b);
        int len1,len2;
        len1=len2=0;
        while(a>0)
        {
            binary1[len1++]=a%2;
            a=a/2;
        }
        while(b>0)
        {
            binary2[len2++]=b%2;
            b=b/2;
        }
        int maxlen=max(len1,len2);
        LL ans=0;
        for(int k=maxlen-1;k>=0;k--)
        {
            if(binary1[k]==binary2[k])
            {
                if(binary1[k]==1)
                    ans+=(LL)pow(2,k);
            }
            else
            {
                ans+=(LL)pow(2,k+1)-1;
                break;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

转换成二进制  左边和右边相等 是1 显然 这一位可以取1

不相等可以转化成比小的那个大  然后都是1 后面都是1

LL

HDU 5969