Codeforces 165E Compatible Numbers

题目链接：https://codeforces.com/contest/165/problem/E

1 题目大意

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

对于每一个 ai，询问是否存在 aj 使得 ai&aj=0，如果有输出 aj（如果有多个，输出任意一个），否则输出 −1。

1≤n≤106,1≤ai≤4⋯106。

注意到 ai&aj=0，其实就是询问是否有数字满足其是 ai 的补集的子集。

SOS DP 求出每个集合是否有数字是其子集即可。

3 Code

/*
 * e.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;

int a[ 1 << K ];
int f[ 1 << K ];

int main() {
    int n = read<int>();
    memset( f, -1, sizeof(f) );
    for( int i = 1; i <= n; i ++ ) {
        a[i] = read<int>();
        f[ a[i] ] = a[i];
    }
    for( int j = 0; j < K; j ++ ) 
        for( int i = 0; i < ( 1 << K ); i ++ ) 
            if( i & ( 1 << j ) )
                chk_Max( f[i], f[ i ^ ( 1 << j ) ] );
    const int mask = ( 1 << K ) - 1;
    for( int i = 1; i <= n; i ++ ) {
        printf( "%d ", f[ a[i] ^ mask ]  );
    }
}