题目链接：https://codeforces.com/contest/1208/problem/F

1 题目大意

给定一个长度为 n 的序列 a

求最大 ai|(aj&ak) 满足 i<j<k

3≤n≤106,0≤ai≤2⋅106

先考虑 aj&ak，显然可以通过 SOS DP 来求出对于任意 s，其最靠后 j 的能够有 k 使得 s⊆aj&ak 的位置。

然后考虑贪心来最大化按位或，从高位往低位处理，如果能够有一位新为 1，则有限选择位数高的。

3 Code

/*
 * f.cpp
 * Copyright (C) 2022 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU AGPLv3+ license.
 */

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>

typedef long long ll;
typedef unsigned long long ull;

inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
template <class T> 
T Max( T a, T b ) { return a > b? a: b; }
template <class T> 
T Min( T a, T b ) { return a < b? a: b; }
template <class T> 
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T> 
void chk_Min( T &a, T b ) { if( b < a ) a = b; }
template <typename T>
T read() { 
    T sum = 0, fl = 1; 
    char ch = getchar();
    for (; isdigit(ch) == 0; ch = getchar())
        if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
    return sum * fl;
}
template <class T> 
T pow( T a, int p ) {
    T res = 1;
    while( p ) {
        if( p & 1 ) 
            res = res * a;
        a = a * a;
        p >>= 1;
    }
    return res;
}/*}}}*/

const int K = 22;
const int N = ( 1 << K ) + 10;

int a[N];
int f[N][2];

int full_pow( const int cur ) { return 1 << cur; }
bool chk_pos( const int cur, const int p ) { return cur & full_pow(p); }

void set( const int pos, const int val ) {
    if( val > f[pos][0] ) {
        f[pos][1] = f[pos][0];
        f[pos][0] = val;
    }
    else if( val != f[pos][0] && val > f[pos][1] ) {
        f[pos][1] = val;
    }
}

int main() {
#ifdef woshiluo
    freopen( "f.in", "r", stdin );
    freopen( "f.out", "w", stdout );
#endif
    int n = read<int>();
    for( int i = 1; i <= n; i ++ ) {
        a[i] = read<int>();
        set( a[i], i );
    }

    for( int st = full_pow(K) - 1; st >= 0; st -- ) {
        for( int i = 0; i < K; i ++ ) {
            if( chk_pos( st, i ) ) {
                set( st ^ full_pow(i), f[st][1] );
                set( st ^ full_pow(i), f[st][0] );
            }
        }
    }

    int ans = 0;
    for( int i = 1; i <= n - 2; i ++ ) {
        const int cur = a[i];
        int mask = 0;
        for( int j = K - 1; j >= 0; j -- ) {
            if( chk_pos( cur, j ) )
                continue;
            if( f[ mask ^ full_pow(j) ][1] > i )
                mask |= full_pow(j);
        }
        chk_Max( ans, cur | mask );
    }
    printf( "%d\n", ans );
}

class

OI

local_offer

dp

发表评论 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注