Problem Description
B君和G君聊天的时候想到了如下的问题。
给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。
其中|表示按位或,即C、 C++、 Java中的|运算。
给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。
其中|表示按位或,即C、 C++、 Java中的|运算。
Input
包含至多10001组测试数据。
第一行有一个正整数,表示数据的组数。
接下来每一行表示一组数据,包含两个整数l,r。
保证 0 <= l <= r <= 1018。
第一行有一个正整数,表示数据的组数。
接下来每一行表示一组数据,包含两个整数l,r。
保证 0 <= l <= r <= 1018。
Output
对于每组数据输出一行,表示最大的位或。
题目是中文的题意就不解释了
大致还是贪心的思想,两个数异或有1就是1都是0才是0。
这题我们只要考虑两种情况就可以了。一种是当他们都化为二进制时,比较一下位数如果他们的位数相差1以上的话直接将所有位数都变成1。
第二种当他们位数相同时也是最难考虑的情况,从高位向低位遍历,遇到相同位为1的时候继续向下查找知道为1的位不相同时,将位小的为1
以后的全变成1。大致如何实现还是看代码,语言表达能力较差,不好解释。
#include <iostream> #include <cstring> #include <cmath> using namespace std; typedef long long ll; int dig1[70] , dig2[70] ,dig3[70]; void Get(ll x , int dig[] , int &gg) { int len = 0; if(x == 0) { len = 1; } while(x) { dig[++len] = x % 2; x >>= 1; } gg = len; } ll Pow(int x , int y) { ll sum = 1; for(int i = 1 ; i <= y ; i++) { sum *= x; } return sum; } int main() { int t; cin >> t; while(t--) { ll l , r; memset(dig1 , 0 , sizeof(dig1)); memset(dig2 , 0 , sizeof(dig2)); memset(dig3 , 0 , sizeof(dig3)); cin >> l >> r; int len1 = 0 , len2 = 0; Get(l , dig1 , len1); Get(r , dig2 , len2); if(len1 == len2) { int temp1 = 0; int temp2 = 0; int flag = 0; for(int i = len2 ; i >= 1 ; i--) { if(dig2[i] == 1 && flag == 0) { temp1 = i; } if(dig1[i] == 1) { temp2 = i; if(flag == 1) break; } if(temp1 == temp2) { ; } else { flag = 1; temp2 = temp1 - 1; } } if(temp1 == temp2) { for(int i = len2 ; i >= 1 ; i--) { dig3[i] = dig2[i]; } } else { for(int i = len2 ; i >= 1 ; i--) { if(i > temp1) { dig3[i] = dig2[i]; } else { dig3[i] = 1; } } } } if(len1 < len2) { for(int i = len2 ; i >= 1 ; i--) { dig3[i] = 1; } } ll sum = 0; for(int i = 1 ; i <= len2 ; i++) { sum += Pow(2 , i - 1) * dig3[i]; } cout << sum << endl; } return 0; }