题解：CF1688A Cirno's Perfect Bitmasks Classroom
首先暴力肯定是不行的，对于一个 $x=2^k$ 的数一定会被卡到超时。
由于题目寻找最小的数 $y$ 符合 $x \& y > 0$ 且 $x \oplus y > 0$，不难想到先用 $\mathrm{lowbit}$ 找到符合 $x \oplus y > 0$ 的 $y$。发现只要 $x \neq y$，显然也满足前者的条件。值得注意的是，当 $x = 1$ 时的答案比较特殊，因此特判即可。
因此，我们分为三类考虑，得到最终的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int t,n,m;
int main ()
{
t = read ();
while (t--)
{
n = read ();
if (n == 1)
{
printf ("3\n");
continue;
}
m = n & (-n);
if (m == n) ++m;
printf ("%d\n",m);
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
