You are given an array aa of nn integers.
You need to find the maximum value of ai|(aj&ak)ai|(aj&ak) over all triplets (i,j,k)(i,j,k) such that i<j<ki<j<k.
Here && denotes the bitwise AND operation, and || denotes the bitwise OR operation.
The first line of input contains the integer nn (3≤n≤1063≤n≤106), the size of the array aa.
Next line contains nn space separated integers a1a1, a2a2, ..., anan (0≤ai≤2⋅1060≤ai≤2⋅106), representing the elements of the array aa.
Output a single integer, the maximum value of the expression given in the statement.
3 2 4 6
6
4 2 8 4 7
12
In the first example, the only possible triplet is (1,2,3)(1,2,3). Hence, the answer is 2|(4&6)=62|(4&6)=6.
In the second example, there are 44 possible triplets:
The maximum value hence is 1212.
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = (1 << 24); const int M = 23; int n, cnt[maxn]; inline void update(ll cur, int pos = 0) { if (cnt[cur] >= 2)return; cnt[cur]++; for (register int i = pos; i <= M; ++i) { if (cur & (1 << i)) { update(cur ^ (1 << i), i); } } } int main() { //freopen("1.txt", "r", stdin); scanf("%d", &n); vector<ll> e(n); for (auto &i : e) { scanf("%lld", &i); } //for(register int i=0;i<3;++i)printf("%lld\n",e[i]); update(e[n - 1]); update(e[n - 2]); ll res = 0; for (register int i = n - 3; i >= 0; --i) { ll head = e[i]; int nx = 0; for (register int j = M; j >= 0; --j) { if (!(head & (1 << j)) && cnt[nx | (1 << j)] >= 2) { nx |= (1 << j); } //printf("debug res = %lld\n",res); } res = max(res, head | nx); update(e[i]); } printf("%lld\n", res); return 0; }
Bits And Pieces
原文：https://www.cnblogs.com/czy-power/p/11411187.html
