HDoj 5969最大ビットまたは(ビットまたは)
2268 ワード
最大ビットまたは
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1182 Accepted Submission(s): 477
Problem Description
B君がG君と話している間に次のような質問をした.
自然数lとrを与え、2つの整数xを選択し、yはl<=x<=y<=rを満たし、x|yが最大となる.
ここで、|はビットまたは、すなわちC、C++、Javaにおける|演算を表す.
Input
10001までのテストデータが含まれます.
最初の行には、データのグループ数を表す正の整数があります.
次に、各行は、2つの整数l,rを含むデータのセットを表す.
保証0<=l<=r<=
1018.
Output
データのセットごとに1行出力され、最大のビットまたはを表します.
Sample Input
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1182 Accepted Submission(s): 477
Problem Description
B君がG君と話している間に次のような質問をした.
自然数lとrを与え、2つの整数xを選択し、yはl<=x<=y<=rを満たし、x|yが最大となる.
ここで、|はビットまたは、すなわちC、C++、Javaにおける|演算を表す.
Input
10001までのテストデータが含まれます.
最初の行には、データのグループ数を表す正の整数があります.
次に、各行は、2つの整数l,rを含むデータのセットを表す.
保証0<=l<=r<=
1018.
Output
データのセットごとに1行出力され、最大のビットまたはを表します.
Sample Input
5 1 10 0 1 1023 1024 233 322 1000000000000000000 1000000000000000000
Sample Output
15 1 2047 511 1000000000000000000
思路：位或：有1 为1 ，全0 为0。 位或的最大值，右边界一定会取到，左边界二进制位数没有右边界多时补0，从高位到低位遍历，
当同为1 是出1 ，ans进行累加；当同为0时，不加；当右边界为1，左边界为0是，ans累加，并且左边界后的数全部赋值为1
code
#include
#include
#include
#include
using namespace std;
int main()
{
int n,a[100],b[100];
long long l,r;
scanf("%d",&n);
for(int i=0;i=0;i--)
{
if(a[i]==1&&b[i]==1)
sum+=(long long)pow(2,i);
else if(a[i]==1&&b[i]==0)
{
sum+=(long long)pow(2,i+1)-1;
break;
}
}
printf("%lld
",sum);
}
}
return 0;
}