原题:CF1208F
记为的补集。
30分:考虑从大到小枚举,然后把所有的子集全部标记出来,这个显然可以记忆化一下,也就是一旦一个点之前被标记了,就不需要再下传标记了,复杂度是,之后就是传统的对于的按位贪心的套路了。
额外20分:
考虑对于每一个数字,我们把所有的子集出现的次数都。
那么对于来说,所有出现次数的数字都是可以用到的。
所以我们直接枚举每个数字,给它的子集都,就可以完成查询。
一个剪枝是,出现次数超过两次的数字我们不需要再次添加,复杂度,是二进制的位数。
100分:
方法1:我们结合前面的做法。
考虑对于每一个数字,我们把所有的子集出现的次数都。
那么对于来说,所有出现次数的数字都是可以用到的。
考虑到数字范围只有,我们直接记忆化地给子集添加就可以了,这样添加的均摊复杂度是。
void add(int x,int y)//添加子集个数 x数字 y当前标记
{
if(sum[x] > 1|| vis[x] == y) return;//个数超过一个(没有意义)或者已被访问
++sum[x];//统计
vis[x] = y;//标记
for(int i = 0;(1 << i-1) < x;++i)
if(x & (1 << i))
add(x ^ (1 << i),y);//枚举子集
}
方法2:
我们直接用来表示二进制下是超集的数字里面,最晚出现的位置,和次晚出现的位置。
那么对于一个来说,我们直接按位贪心当前的答案,如果就说明是合法的。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn];
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<48||ch>57){if(ch==45)y=-1;ch=getchar();}
while(ch>=48&&ch<=57)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*y;
}
int mx[(1<<21)],cx[(1<<21)];
inline void update(int k,int x){
if(mx[k]<x){cx[k]=mx[k];mx[k]=x;}
else if(mx[k]==x)cx[k]=x;
else cx[k]=max(cx[k],x);
return ;
}
void sos(int len){
for(int i=0;i<21;i++)
for(int j=0;j<len;j++)
if(!(j&(1<<i))){
update(j,mx[j^(1<<i)]);
update(j,cx[j^(1<<i)]);
}
return ;
}
int main(){
int n;
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
update(a[i],i);
}
sos(1<<21);
// for(int i=1;i<(1<<21);i++)cout<<i<<" "<<mx[i]<<" "<<cx[i]<<endl;
int S=(1<<21)-1,ans=0;
for(int i=1;i<=n-2;i++){
int c=S^a[i];
int s=0;
for(int j=21;j>=0;j--){
if(!((c>>j)&1))continue;
s+=(1<<j);
if(cx[s]<=i)s-=(1<<j);
}
ans=max(ans,a[i]+s);
}
printf("%d\n",ans);
return 0;
}