首页 > 试题广场 >

CodeForces 484A Bits

[编程题]CodeForces 484A Bits

热度指数：29 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

Let's denote as $\text{[math]}$ 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 $\text{[math]}$ is maximum possible. If there are multiple such numbers find the smallest of them.

输入描述:

The first line contains integer n — the number of queries (1 ≤ n ≤ 10000).

Each of the following n lines contain two integers l_i, r_i — the arguments for the corresponding query (0 ≤ l_i ≤ r_i ≤ 10¹⁸).

输出描述:

For each query print the answer in a separate line.

示例1

输入

3<br />1 2<br />2 4<br />1 10<br />

输出

1<br />3<br />7<br />

备注:

The binary representations of numbers from 1 to 10 are listed below:
1₁₀ = 1₂
2₁₀ = 10₂
3₁₀ = 11₂
4₁₀ = 100₂
5₁₀ = 101₂
6₁₀ = 110₂
7₁₀ = 111₂
8₁₀ = 1000₂
9₁₀ = 1001₂
10₁₀ = 1010₂

算法知识视频讲解

C/C++

梦樱羽

典型的位运算

需要注意的是，由于数据规模很大，用log2函数会产生超过1e-9以上的误差

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)

#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl

#define LOWBIT(x) ((x)&(-x))

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

#define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))
#define msM(a) memset(a,-1,sizeof(a))

#define pii pair<int,int> 
#define piii pair<pair<int,int>,int> 
#define mp make_pair
#define pb push_back
#define fi first
#define se second

inline int gc(){
    static const int BUF = 1e7;
    static char buf[BUF], *bg = buf + BUF, *ed = bg;
    
    if(bg == ed) fread(bg = buf, 1, BUF, stdin);
    return *bg++;
} 

inline int ri(){
    int x = 0, f = 1, c = gc();
    for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
    for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
    return x*f;
}

typedef long long LL;
typedef unsigned long long uLL;
const double EPS = 1e-9;
const int inf = 1e9 + 9;
const LL mod = 1e9 + 7;
const int maxN = 1e5 + 7;
const LL ONE = 1;

int n;
LL l, r, ans;
// lbit ： l的二进制位数 
// rbit ： r的二进制位数 
// hbit ： r的最高二进制位
LL lbit, rbit, hbit;

// 二分计算x的二进制位数 
inline int getBits(LL x) {

	    int cnt = 1;



	    while((x >> 1) != 0) {



	        ++cnt;



	        x >>= 1;



	    }



	    return cnt;

} 

// 取x的最高二进制位 
inline LL HighBit(LL x) {
    while(x & (~LOWBIT(x)) != 0) x &= ~LOWBIT(x);
    return x;
} 

int main(){
    cin >> n;
    while(n--) {
        cin >> l >> r;
        ans = 0;
        if(r == 0) {
            cout << ans << endl;
            continue;
        }
        if(l == 0) ++l;
        
        lbit = getBits(l);
        rbit = getBits(r);
        hbit = ONE << (rbit - 1);
        
        // 把相同的高二进制位取下来 
        while(lbit == rbit) {
            l &= hbit - 1;
            r &= hbit - 1;
            ans += hbit;
            if(r == 0) break;
            if(l == 0) ++l;
            lbit = getBits(l);
            rbit = getBits(r);
            hbit = ONE << (rbit - 1);
        }
        if(r == 0) {
            cout << ans << endl;
            continue;
        }
        
        if(getBits(r + 1) > rbit) ans += r; // 如果r是11111，那直接选r 
        else ans += hbit - 1; // 否则选01111 
        
        cout << ans << endl;
    }
    return 0;
}

/*
1
7849325874389577 8477432355483974

ans:7881299347898367
*/

编辑于 2019-04-17 08:28:08 回复(0)