link

「NOIP2021模拟赛 By JXC C」位运算

sol

通过观察我们发现， \(i\) 对答案的限制比较小，所以考虑枚举 \(i\)

从后往前枚举 \(i\) ，然后从高到低枚举位,若 \(i\) 的一位上是 \(1\)，那么 \(ans\) 在这一位上可以是 \(1\) ，若是 \(0\) ，那么需要到后面来找两个数的子集 满足 这一位上是 \(1\) ,由于是从大到小枚举的，所以看到 \(1\) 取就好了

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=8e6+5;
int N,ans,a[maxn],mp[maxn],st[maxn],top,vis[maxn];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
void add_x(int x){
	if(mp[x]>=2||vis[x])return ;
	++mp[x];vis[x]=1;st[++top]=x;
	for(int i=22;i>=0;i--) if(x>>i&1) add_x(x^(1<<i));
}
int query(int x){
	int sum=0,now=0;
	for(int i=22;i>=0;i--){
		if(x>>i&1) sum|=1<<i;
		else if(mp[now|(1<<i)]>=2) sum|=1<<i,now|=1<<i;
	}
	return sum;
}
int main(){
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
	N=read();
	for(int i=1;i<=N;i++) a[i]=read();
	for(int i=N;i>1;i--){
		add_x(a[i]);
		if(N-i>=1) ans=max(ans,query(a[i-1]));
		while(top) vis[st[top--]]=0;
	}
	printf("%d\n",ans);
	return 0;
}