Codeforces F. Bits And Pieces(位运算)

时间:2023-02-07 05:00:32

传送门.

位运算的比较基本的题。

考虑枚举\(i\),然后二进制位从大到小考虑, 对于第\(w\)位,如果\(a[i][w]=1\),那么对\(j、k\)并没有什么限制。

如果\(a[i][w]=0\),那么我们希望\((a[j]~and~a[k])[w]=1\),结合前面的限制,就是给定\(x\),问有没有\(x∈a[j]~and~a[k](i<j<k)\)。

那么这应该是做一个高维后缀max和次max就能解决的事。

Code:


#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define ff(i, x, y) for(int i = x; i < y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
#define pp printf
#define ll long long
using namespace std; const int N = 1e6 + 10; int n, a[N]; const int M = 1 << 21; int f[M], g[M]; void add(int x, int i) {
if(x > f[i]) {
g[i] = f[i];
f[i] = x;
} else
if(x > g[i]){
g[i] = x;
}
} const int inf = 1e9; int main() {
scanf("%d", &n);
fo(i, 1, n) {
scanf("%d", &a[i]);
add(i, a[i]);
}
fo(i, 0, 20) {
ff(j, 0, 1 << 21) {
if(!(j >> i & 1)) {
add(f[j + (1 << i)], j);
add(g[j + (1 << i)], j);
}
}
}
ff(j, 0, 1 << 21) {
if(f[j] != g[j]) {
f[j] = g[j];
} else {
f[j] = 0;
}
}
int ans = 0;
fo(i, 1, n - 2) {
int x = 0;
fd(j, 20, 0) {
if(!(a[i] >> j & 1)) {
x += 1 << j;
if(g[x] <= i) {
x -= 1 << j;
}
}
}
ans = max(ans, x | a[i]);
}
pp("%d", ans);
}