Codeforces Round #276 (Div. 2) - c++编程基础

C. Bits time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Let's denote as $\$ the number of bits set ("1' bits) in the binary representation of the non-negative integer x.

You are given multiple queries consisting of pairs of integers l and r. For each query, find the x, such that l?≤?x?≤?r, and $\$ is maximum possible. If there are multiple such numbers find the smallest of them.

Input

The first line contains integer n ― the number of queries (1?≤?n?≤?10000).<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CkVhY2ggb2YgdGhlIGZvbGxvd2luZyA8ZW0+bjwvZW0+IGxpbmVzIGNvbnRhaW4gdHdvIGludGVnZXJzIDxlbT5sPC9lbT48ZW0+aTwvZW0+LD88ZW0+cjwvZW0+PGVtPmk8L2VtPiChqgogdGhlIGFyZ3VtZW50cyBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgcXVlcnkgKDA/odw/PGVtPmw8L2VtPjxlbT5pPC9lbT4/odw/PGVtPnI8L2VtPjxlbT5pPC9lbT4/odw/MTAxOCkuPC9wPgoKCgpPdXRwdXQKPHA+CkZvciBlYWNoIHF1ZXJ5IHByaW50IHRoZSBhbnN3ZXIgaW4gYSBzZXBhcmF0ZSBsaW5lLjwvcD4KCgoKU2FtcGxlIHRlc3QocykKCgoKaW5wdXQKPHByZSBjbGFzcz0="brush:java;">3 1 2 2 4 1 10 output

1
3
7

Note

The binary representations of numbers from 1 to 10 are listed below:

110?=?12

210?=?102

310?=?112

410?=?1002

510?=?1012

610?=?1102

710?=?1112

810?=?10002

910?=?10012

1010?=?10102

看了我的代码，自己对照模拟下就知道思路了：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; __int64 bit[65]; int main() { bit[0]=1; for(int i = 1; i <= 63; i++) { bit[i] = 2*bit[i-1]; } int n; scanf("%d",&n); while(n--) { __int64 l,r; scanf("%I64d%I64d",&l,&r); int j; __int64 sum = 0; for(j = 0; sum <=r; j++) { sum += bit[j]; } j--; while(sum > r) { sum -= bit[j]; if(sum < l) sum += bit[j]; j--; } printf("%I64d\n",sum); } return 0; }