题意：
给定长度为n的序列a
计算max(a[i]|(a[j]&a[k])),其中i<j<k
数据范围：n<=1e6，a(i)<=2e6
解法：
考虑枚举a[i],找最大的a[j]&a[k]1.做法1:
因为要保证i<j<k,所以倒着插入,因为我们要找的是用来与|的,
所以Sosdp记录每个mask的超集信息,那么插入x则是往x的子集插,
注意:在剪枝条件下,插入函数别写错了,如果子集插少了就wa了.
插入函数是"递归"实现的,具体看代码.
查询的时候贪心第从高位到低位判断能否取到,
如果超集数量>=2则能,否则不能2.做法2:
超集Sosdp,记录每种状态超集的最大的两个下标,
枚举a[i]查询的时候,判断是否超集的两个下标都大于当前i就行了总结:
递归插入是要插入所有子集的,
在我的想法里,理论上二进制位有一个1,子集数量就*2,那么子集大小不是指数级的了吗??
多插几个数就凉了,所以这题要有剪枝,d[x]>=2的时候就退出,保证每个位置不被插超过两次.
这么看来还是第二种做法比较举有适应性.参考:
1.做法1
https://blog.csdn.net/weixin_45564571/article/details/100130070
2.做法2
https://www.cnblogs.com/GavinZheng/p/11534007.html
code1：
#include<bits/stdc++.h>
using namespace std;
const int maxm=4e6+5;
int d[maxm];
int a[maxm];
int n;
void add(int x,int k){//按位插入if(d[x]>=2)return ;//不剪枝会tleif(k==-1){d[x]++;//到最后一层的时候d[x]++;return ;}if(x>>k&1){//如果是1则可以删1add(x,k-1);//不删add(x^(1<<k),k-1);//删}else{//如果是0则不能删add(x,k-1);//只能不删}
}
int ask(int x){int ans=0;for(int i=21;i>=0;i--){//贪心地从高位选if(!(x>>i&1)&&d[ans|(1<<i)]>=2){ans|=(1<<i);}}return x|ans;
}
signed main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int ans=0;for(int i=n;i>=1;i--){if(i<=n-2){ans=max(ans,ask(a[i]));}add(a[i],21);}printf("%d\n",ans);return 0;
}
code2：
#include<bits/stdc++.h>
using namespace std;
const int maxm=4e6+5;
struct Node{int a,b;//最大和次大
}d[maxm];
int a[maxm];
int n;
void add(int x,int id){if(id>d[x].a){d[x].b=d[x].a;d[x].a=id;}else if(id>d[x].b){d[x].b=id;}
}
void init(){for(int i=1;i<=n;i++){add(a[i],i);}for(int i=0;i<22;i++){for(int j=(1<<21);j>=0;j--){if(j>>i&1){//更新子集add(j^(1<<i),d[j].a);add(j^(1<<i),d[j].b);}}}
}
int ask(int x,int id){int ans=0;for(int i=21;i>=0;i--){if(!(x>>i&1)&&d[ans^(1<<i)].b>id){ans|=(1<<i);}}return x|ans;
}
signed main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}init();int ans=0;for(int i=1;i<=n-2;i++){ans=max(ans,ask(a[i],i));}printf("%d\n",ans);return 0;
}