题意
题目链接。
给你一个由 $n$ 个整数组成的数组 $a$ 。
你需要在所有三元组 $(i,j,k)$ 中找出 $a_{i} | ( a_{j} \& a_ {k} )$ 的最大值,使得 $i < j < k$ .
这里 $\&$ 表示 位与运算,而 $|$ 表示 位与运算。
由 Codeforces Better! 根据 DeepL 翻译。
解析
考虑 SOS dp。
用 $dp_{mask}$ 表示 $mask$ 及其超集中的所有状态的最右边的两个数,即这两个数的 $\&$ 为 $mask$ 或其超集中的某一个状态。
那么,我们依次枚举 $a_i$,然后取其逐位取反后的数 $(1<<bits)\oplus a_i$,再从高到低逐位尝试,即判断加入该位后的 $dp_{mask}$ 中的两个数是否都在 $i$ 右侧即可。
代码
#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
const int N=3e6+5;
pi dp[N];
int n,a[N],bits,ans;
void add(int mask,int pos){
if(!dp[mask].fi) dp[mask].fi=pos;
else if(!dp[mask].se){
// if(pos==dp[mask].fi) return;
dp[mask].se=pos;
if(dp[mask].fi>dp[mask].se) swap(dp[mask].fi,dp[mask].se);
}
else if(pos>dp[mask].se){
dp[mask].fi=dp[mask].se;
dp[mask].se=pos;
}
else if(pos>dp[mask].fi){//&&pos!=dp[mask].se
dp[mask].fi=pos;
}
}
void merge(int mask,int orimask){
add(mask,dp[orimask].fi);
add(mask,dp[orimask].se);
}
signed main(){
scanf("%d",&n);
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
bits=max(bits,(int)log2(a[i]));
add(a[i],i);
}
bits++;
for(int i=0;i<bits;i++)
for(int sta=(1<<bits)-1;sta>=0;sta--)
if(!(sta&(1<<i)))
merge(sta,sta^(1<<i));
for(int i=1;i<=n-2;i++){
int complement=a[i]^((1<<bits)-1);
int tmp=0;
for(int j=bits-1;j>=0;j--){
if(complement&(1<<j)){
if(dp[tmp^(1<<j)].se!=-1 && dp[tmp^(1<<j)].fi>i){
tmp^=(1<<j);
}
}
}
// if(dp[tmp].se!=-1 & dp[tmp].fi>i) ans=max(ans,a[i]^tmp);
ans=max(ans,a[i]^tmp);
}
printf("%d\n",ans);
return 0;
}
评论