CF. Bits And Pieces（子集状压dp + 剪枝）

思路：

贪心地从高位到低位考虑，对于任意的i，如果a[i]的第x位是1，那就不用考虑；如果第x位是0，那就希望能找到a[j]和a[k]满足i<j<k，并且a[j] & a[k] = 1。

那么我们可以倒序遍历i，对所有的 j  [i+1, n]，我们把a[j]的子集的出现次数记录在A数组内，比如[i+1,n]范围内的a[j]为 10,11,100（全部写成二进制），那么A[10] = 2，因为有两个数有子集10。

那么，什么时候存在a[j]和a[k]满足i<j<k，并且a[j] & a[k] = 1呢？就是A[mask] >= 2的时候，其中mask中包含了a[i]当前需要补足的所有1。

如果讲的不明白，请看代码：

code1（tle）：

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define debug cout<<111<<endl;
const int N = 1e6+5;
int n, a[N], f[(1<<20)+5], ans=0;

void add(int x,int p){
    if(p==-1) {f[x]++; return;} //所有位都遍历完了，该子集方案数+1
    add(x,p-1); //保留原样，向下add
    if(x&(1<<p)) add(x^(1<<p), p-1); //第p位把1改成0，向下add
}
inline void solve(){
    cin>>n; FOR(i,1,n) cin>>a[i];
    add(a[n],20); add(a[n-1],20);
    for(int i=n-2; i>=1; i--){
        int mask=0;
        for(int j=20; j>=0; j--){
            if(a[i] & (1<<j)) continue; //如果a[i]这位本来就是1，那就不用管
            if(f[mask|(1<<j)] >= 2) mask |= (1<<j); //贪心第j位
        }
        ans = max(ans, a[i]|mask);
        add(a[i],20); //把a[i]也加入到对f的贡献中
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T=1; while(T--) solve();
}

然鹅，这个代码tle了。

为什么呢？因为参数完全相同的add可能进行很多次，但是相同的add进行超过两次之后就不会影响A[mask] >= 2了，所以可以用f[i][j]记录add(i,j)的遍历次数 ，遍历了超过两次直接return掉，完成剪枝。

这是剪枝后的ac代码：

code2（ac）：

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define debug cout<<111<<endl;
const int N = 1e6+5;
int n, a[N], A[N*2], ans=0;
int f[N*2][22];

void add(int x,int p){
    if(p==-1) {A[x]++; return;} //所有位都遍历完了，该子集方案数+1
    if(f[x][p]>=2) return; //这个add已经遍历过两次了，对应的所有A[y]（y是x的子集）至少也是2了，所以剪枝掉
    f[x][p]++; //遍历了一次add(x,p)，记录下来
    add(x,p-1); //保留原样，向下add
    if(x&(1<<p)) add(x^(1<<p), p-1); //第p位把1改成0，向下add
}
inline void solve(){
    cin>>n; FOR(i,1,n) cin>>a[i];
    add(a[n],20); add(a[n-1],20);
    for(int i=n-2; i>=1; i--){
        int mask=0;
        for(int j=20; j>=0; j--){
            if(a[i] & (1<<j)) continue; //如果a[i]这位本来就是1，那就不用管
            if(A[mask|(1<<j)] >= 2) mask |= (1<<j); //贪心第j位
        }
        ans = max(ans, a[i]|mask);
        add(a[i],20); //把a[i]也加入到对f的贡献中
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T=1; while(T--) solve();
}