首页 > 代码库 > Codeforces 484A - Bits 二进制找1
Codeforces 484A - Bits 二进制找1
这题可以根据l, r 在二进制下的长度进行分类。
l 的长度小于 r 的时候，有两种可能，一种是r 在二进制下是 1* 这种样子，故答案取 r ；
一种是取答案为 (1LL << (rcnt - 1)) - 1 ，意思为比 r 小一位长度，也是 1* 这种样子的数。
l 的长度等于 r 的时候，答案从 l 开始找 ， 按位 与 1，同时要满足答案不大于 r 即可。
source code (有参考)：
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int INF = 0x3f3f3f3f;int Cal(long long x){ int ret = 0; while (x){ ++ret; x >>= 1; } return ret;}int main(){ int n; long long l, r, ret; cin >> n; while (n--){ cin >> l >> r; int lcnt = Cal(l); int rcnt = Cal(r); if (lcnt < rcnt){ //for lcnt != rcnt, answer must like 1* to r if (r == (1LL << rcnt) - 1){ ret = r; } else{ ret = (1LL << (rcnt - 1)) - 1; } } else{ //for lcnt == rcnt, answer must be 1* and less than r for (int i = 0; i < rcnt; ++i){ if (((1LL << i) | l) <= r){ l |= (1LL << i); } } ret = l; } cout << ret << endl; } return 0;}
Codeforces 484A - Bits 二进制找1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。