hduoj-5969【位运算】【贪心】

题目链接：​​点击打开链接​​

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1179Accepted Submission(s): 475

Problem Description

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

Input

包含至多10001组测试数据。
第一行有一个正整数，表示数据的组数。
接下来每一行表示一组数据，包含两个整数l,r。
保证 0 <= l <= r <= 1018。

Output

对于每组数据输出一行，表示最大的位或。

Sample Input

5 1 10 0 1 1023 1024 233 322 1000000000000000000 1000000000000000000

Sample Output

15 1 2047 511 1000000000000000000

Source

​​2016年中国大学生程序设计竞赛（合肥）-重现赛（感谢安徽大学）​​

思路：

1、考虑贪心，或运算运算规则：

有1为1，否则为0.

那么贪心关键的角度，就是如何让得到的数尽可能大，并且1尽可能的多。

2、那么考虑将数值转化成二进制上来解决问题：

①我们从高位开始枚举，枚举一个比l大，比r小的，并且和r同长度的一个数。

假设r==10001001011101，那么我们第一个枚举出来的数就是10000000000000，接下来枚举1000100000000.........

依次类推。

②很显然，如果一个数是10000000000000，那么想要和一个数或，使得结果尽可能的大，那么一定是用该数去或该数-1.即10000000000000|1111111111111。

③那么我们在枚举的过程中，维护一个最大（枚举值|当前枚举值-1）即可。

3、结果就是维护的最大值和r中取最大。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
LL l,r;
LL bits[66];
int main()
{
  bits[0]=1;
  for(int i=1;i<=62;i++)
    bits[i]=bits[i-1]*2;
  int t;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%lld%lld",&l,&r);
    LL maxn=0;
    LL ans=r;
    for(int i=62;i>=0;i--)
    {
      if((r&bits[i])!=0)
      {
        maxn+=bits[i];
        if(maxn-1>=l)
          ans=max(ans,(maxn|(maxn-1)));
      }
    }
    printf("%lld\n",max(ans,maxn));
  }
  return 0;
}