CF484A Bits


CF484A Bits

题目

https://codeforces.com/problemset/problem/484/A

题解

思路

知识点:贪心,位运算。

每位独立考虑,要使 /(1/) 的数量最大,且答案最小,因此从低位开始遍历,在不超过 /(r/) 的情况下把 /(l/) 每位变 /(1/) 。

(一开始直接写了个结论,但太烦了qwq)

时间复杂度 /(O(1)/)

空间复杂度 /(O(1)/)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

/*
bool solve() {
    long long l, r;
    cin >> l >> r;
    long long tmp = l ^ r;
    int pos = -1;
    while (tmp) {
        pos++;
        tmp >>= 1;
    }
    cout << (!~pos || ((1LL << pos) - 1 | r) == r ? r : ((l & r) | (1LL << pos) - 1)) << '/n';
    return true;
}
*/

bool solve() {
    long long l, r;
    cin >> l >> r;
    for (int i = 0;i < 63;i++) {
        if ((l | (1LL << i)) <= r)l |= (1LL << i);
        else break;
    }
    cout << l << '/n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '/n';
    }
    return 0;
}

原创文章,作者:506227337,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/268128.html

(0)
上一篇 2022年6月19日 03:50
下一篇 2022年6月19日 03:51

相关推荐

发表回复

登录后才能评论