Maximum

Accept:5     Submit:24

Time Limit:1000MS     Memory Limit:65536KB

Description

Define f(x) as the number of 1s under base 2. For instance, f(5)=2 for (5)10=(101)2, and f(7)=3 for (7)10=(111)2.

Given [A,B], you're required to figure out the maximum f(x) where x is in range [A,B].

Input Format

An integer T(T≤100) will exist in the first line of input, indicating the number of test cases.

Each test case consists of two integers A,B(1≤A,B≤108).

Output Format

Output the maximum f(x) for each test case, one per line.

Sample Input

1

4 6

Sample Output

2

 

新生排位赛第四场的B题，当时还是费了一点脑筋的，比赛到两个多小时的时候才想出来。

题意大概是：定义了一个函数f(x)，表示x的二进制表示中1的个数。给定一个区间[A,B]，求区间内f(x)的最大值。

刚开始总想着把所有数的f(x)都求出来，然后再在给定的区间内搜索。后来试了几种方法，把所有的f(x)都求出来最快的算法还要1.5s左右，必然超时，于是转换思路（说实话，这里数位DP给了我一定的启发，虽然这题和数位DP没什么关系）

对于一个给定的区间[A,B]，可以把A和B都表示成二进制的形式，例如：

　　B:1010011

　　A:1001001

然后从高位到低位开始查找，找到A与B第一个不同的位(在这里即第三位)。

随后把这个不同的位写成0，后面的所有位都写成1，这样就得到了[A,B]区间内二进制表示形式下1最多的那个数（此例中即为1001111）。

但是这样做还有一个需要特别注意的地方，就是当B的不同位后面都是1时，这个不同位是不需要换成0的（因为它保留为1仍在[A,B]区间内），例如：

　　B:1011111

　　A:1001001

这时含1最多的数就是1011111而不是1001111了。

代码很容易写出……

 

1 #include
      
        2 #include
       
         3  4 using namespace std; 5  6 int as[33],bs[33],cs[33]; 7  8 bool all_1(int x) 9 {10     for(int i=x;i>=1;i--)11         if(bs[i]!=1)12             return false;13     return true;14 }15 16 int main()17 {18     int t;19 20     scanf("%d",&t);21 22     while(t--)23     {24         int i;25         long a,b;26 27         scanf("%ld %ld",&a,&b);28         if(a>b)29             a^=b^=a^=b;30         for(i=1;a;++i)31         {32             as[i]=a&1;33             a>>=1;34         }35         for(;i<=32;++i)36             as[i]=0;37         for(i=1;b;++i)38         {39             bs[i]=b&1;40             b>>=1;41         }42         for(;i<=32;i++)43             bs[i]=0;44         for(i=32;as[i]==bs[i];i--)45             cs[i]=as[i];46         if(all_1(i-1))47             for(;i>=1;i--)48                 cs[i]=bs[i];49         else50         {51             cs[i]=0;52             for(--i;i>=1;i--)53                 cs[i]=1;54         }55         int ans=0;56         for(i=1;i<=32;i++)57             if(cs[i]==1)58                 ans++;59         printf("%d\n",ans);60     }61 62     return 0;63 }