EOJ3303 1 的个数最多的整数

Input

第一行一个整数 T (1≤T≤104)，表示问题数。

接下来 T 行，每行两个整数 a,b (0≤a≤b≤263−1)。数据之间用一个空格分隔。

共有两组数据，分别为小数据和大数据，大数据范围如上。对于小数据：T≤10,a≤b≤5⋅106。

Output

对于每个问题，输出一行 Case x: y，其中 x 是问题编号，从 1 开始，y 是答案。

3
0 14
100 1000
3966869755091699093 4597827455649079876

Case 1: 7
Case 2: 511
Case 3: 4035225266123964415

Note

第一个样例数据：a=0,b=14，在 [0,14] 之间含 1 最多的整数为 7(0111),11(1011),13(1101),14(1110)，输出最小的整数为 7。

注意，第三组样例不会出现在小数据中。

题解：

再次感叹一下位运算的神奇

好了中文题意不解释，耿直枚举肯定会超时考虑位运算。

因为要求大于a的最小又要求1最多，那么观察a的二进制从低向高不断的把0变成1就可以了

找出那个比b小的输出即可。

那么用bitset可以很方便地实现。

这里的话再提供一个不用转二进制处理的方法。

直接ans|ans + 1就可以把最低的那个0变成1，神奇啊！

然而我爱bitset

#include <bits/stdc++.h>
using namespace std;
ll w[70];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;w[0] = 1;for(int i = 1; i <= 64; i++)w[i] = w[i - 1] << 1;for(int i = 1; i <= t; i++){ll a, b;cin >> a >> b;ll ans = a, maxnum = 0;bitset<70> temp = bitset<70>(a);for(int i = 0; i < 64; i++){if(temp[i] == 0)ans += w[i];if(ans > b){ans -= w[i];break;}}cout << "Case " << i << ": ";cout << ans << endl;}return 0;
}