CodeForces 485C – Bits [二进制]

点击打开codeforces题目链接

题意

给你一个区间[l, r],让你在这个区间内找出一个数,其二进制表示中‘1’的个数最多

分析

这题考察二进制‘或’的性质,可以贪心每次增加一个二进制‘1’位,直到l大于r停止。下面是两种做法

做法一

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

int main() {
    int T; cin >> T;
    while(T--) {
        ll l, r; cin >> l >> r;
        ll t = 1;
        while(l < r) {
            ll cur = l | t;
            if(cur > r) break;
            l = cur;
            t <<= 1;
        }
        cout << l << endl;
    }
    return 0;
}

做法二

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

int main() {
    int T; cin >> T;
    while(T--) {
        long long l, r; cin >> l >> r;
        while((l | (l + 1)) <= r)
            l |= l + 1;
        cout << l << endl;
    }
    return 0;
}

欢迎留言