CF1208F Bits And Pieces 题解

题意

题目链接

给你一个由 $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;
}
本文作者:water_tomato

评论

    发送评论 编辑评论

    |´・ω・)ノ
    ヾ(≧∇≦*)ゝ
    (☆ω☆)
    (╯‵□′)╯︵┴─┴
     ̄﹃ ̄
    (/ω\)
    ∠( ᐛ 」∠)_
    (๑•̀ㅁ•́ฅ)
    →_→
    ୧(๑•̀⌄•́๑)૭
    ٩(ˊᗜˋ*)و
    (ノ°ο°)ノ
    (´இ皿இ`)
    ⌇●﹏●⌇
    (ฅ´ω`ฅ)
    (╯°A°)╯︵○○○
    φ( ̄∇ ̄o)
    ヾ(´・ ・`。)ノ"
    ( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
    (ó﹏ò。)
    Σ(っ °Д °;)っ
    ( ,,´・ω・)ノ"(´っω・`。)
    ╮(╯▽╰)╭
    o(*////▽////*)q
    >﹏<
    ( ๑´•ω•) "(ㆆᴗㆆ)
    😂
    😀
    😅
    😊
    🙂
    🙃
    😌
    😍
    😘
    😜
    😝
    😏
    😒
    🙄
    😳
    😡
    😔
    😫
    😱
    😭
    💩
    👻
    🙌
    🖕
    👍
    👫
    👬
    👭
    🌚
    🌝
    🙈
    💊
    😶
    🙏
    🍦
    🍉
    😣
    Source: github.com/k4yt3x/flowerhd
    颜文字
    Emoji
    小恐龙
    花!
    上一篇
    下一篇