J - Coolbits
基本信息
题解
考虑从高位到低位确定答案。假设现在需要确定第 位的答案,令 表示已经确定第 个数从最高位到第 位要填什么。
如果答案的第 位要填 ,那么区间 必须与 有交集。如果对于所有 都有交集,那么答案的第 位可以填 ,所有的 增加 。
否则答案的第 位只能填 ,我们还要对于第 个数考虑它的第 位填什么。
- 如果 和 没有交集,那第 个数的第 位只能填 。
- 否则看一下 是否在 的范围内,也就是第 位填 ,后面全填 。如果在范围内,因为后面可以全填 ,所以这个数以后就可以不用考虑了,这一位直接填 就行。否则必然有 (如果是 则 ,不可能和 有交集),那只能填 。
复杂度 。
参考代码
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 | #include <bits/stdc++.h>
#define MAXN ((int) 1e5)
#define MAXP 29
using namespace std;
int n, ans, L[MAXN + 10], R[MAXN + 10];
int now[MAXN + 10];
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &L[i], &R[i]);
ans = 0;
memset(now, 0, sizeof(int) * (n + 3));
for (int i = MAXP; i >= 0; i--) {
bool flag = true;
for (int j = 1; j <= n; j++) {
int l = now[j] + (1 << i), r = now[j] + (2 << i) - 1;
// 区间没有交集,答案无法填 1
if (l > R[j] || r < L[j]) { flag = false; break; }
}
if (flag) {
// 答案可以填 1 的情况
ans |= 1 << i;
for (int j = 1; j <= n; j++) now[j] |= 1 << i;
} else {
// 答案只能填 0 的情况,看每个数的第 i 位填什么
for (int j = 1; j <= n; j++) {
int l = now[j] + (1 << i), r = now[j] + (2 << i) - 1;
if (l <= R[j] && r >= L[j]) {
if (l - 1 < L[j]) now[j] |= 1 << i;
}
}
}
}
printf("%d\n", ans);
}
int main() {
int tcase; scanf("%d", &tcase);
while (tcase--) solve();
return 0;
}
|