最大的位或

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

1 10

0 1

1023 1024

233 322

1000000000000000000 1000000000000000000

Sample Output

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 ;

 }

巴特西

hdu 5969 最大的位或

最大的位或

最新文章

热门文章