最大的位或
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 655 Accepted Submission(s): 293
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
//第一次做位运算有关的题目,贪心方案想了好久。。。
#include <stdio.h>
#include <string.h> typedef long long LL; LL l,r,Max;
char bit_l[];
char bit_r[];
char temp[]; LL StrToNum(char s[])//二进制字符变数字
{
int len=strlen(s);
LL ans=,res=;
for (int i=len-;i>=;i--)
{
if (s[i]=='')
ans+=res;
res*=;
}
return ans;
} void NumToStr(LL x)//数字变二进制字符串
{
if (x==)
{
temp[]='';
temp[]='\0';
return ;
}
char s[];
int pos=;
while (x!=)
{
int tt=x%;
if (tt==)
s[pos++]='';
else if (tt==)
s[pos++]='';
x/=;
}
s[pos]='\0';
int i;
for (i=;i<pos;i++)
temp[i]=s[pos--i];
temp[i]='\0';
} int main()
{
int i,j,t;
char test[];
scanf("%d",&t);
while (t--)
{
Max=-;
scanf("%I64d%I64d",&l,&r);
if (l==r)
{
printf("%lld\n",l|r);
continue;
}
NumToStr(l);
strcpy(bit_l,temp);
NumToStr(r);
strcpy(bit_r,temp); strcpy(test,bit_r);
int len_l=strlen(bit_l);
int len_r=strlen(bit_r);
for (i=;i<len_r-len_l;i++)
{
test[i]='';
}
for (j=;j<=len_l;j++)
{
test[i++]=bit_l[j];
}
strcpy(bit_l,test);
for (i=;i<len_r;i++)
{
if (bit_l[i]==''||bit_r[i]=='')
test[i]='';
else
test[i]='';
}
test[i]='\0';
LL res;
res=StrToNum(test);
if (res>Max) Max=res;
//printf("l : %s\n",bit_l);
//printf("r : %s\n",bit_r);
//printf("t : %s\n",test);
int k=;
while (bit_l[k]==bit_r[k]) k++;
k++;
for (i=k;i<len_r;i++)
{
res=StrToNum(test);
if (res>Max) Max=res;
if (bit_l[i]==''&&bit_r[i]=='')
{
test[i]='';
res=StrToNum(test);
if (res>Max)
Max=res;
}
}
printf("%I64d\n",Max);
}
return ;
}