Description

给出个正整数,求

Input

第一行是一个正整数,接下来行每行都会有一个正整数,第行的正整数为

Output

输出一个正整数即

Sample Input

4
1
2
3
4

Sample Output

2

Hint

对于的数据,有

Test_ID n
1 7
2 50
3 1000
4 40000
5 50000
6 60000
7 70000
8 80000
9 100000
10 300000

Solvution

那天在UOJ群上看到Claris在讲这道题,感觉蛮神的,就搬下来了。
考虑把每一个数进行二进制分解,既然要选值最大的,那么我们就可以贪心地从最高位开始选取,如果说有2个以上的数包含这一位,那么答案里就会包含这一位,然后对于每一位我们只要确定有多少个数包含这一位,如果有2个以上,那么接下来就只用在这些包含这一位的数中选取了,否则就选择下一位,接下来每一位都当做最高位选。最后的答案就是剩下来的任意两个的值。
所以复杂度是

Code

代码里我用了 bitset和vector,常数会略高

#include <bits/stdc++.h>

using namespace std;

#define putc(c) ( putchar(c) )
#define getc( ) ( getchar( ) )

template<typename T>inline T read(T &f) {
    f = 0;
    int x = 1;
    char c = getc();
    while(!isdigit(c)) x = (c == '-' ? -1 : 1) , c = getc();
    while(isdigit(c)) f = (f << 1) + (f << 3) + c - '0' , c = getc();
    return f = f * x;
}

template<typename T>inline void write(T f) {
    if(f == 0){ putc('0') ; return; }
    if(f < 0) putc('-') , f = -f;
    static char str[20] , top = 0;
    while(f) str[++top] = f % 10 + '0' , f /= 10;
    while(top) putc(str[top--]);
}

#define writeln(x) write(x) , putc('\n')
#define writesp(x) write(x) , putc(' ')

#define LL long long

const int maxn = 300000 + 5;

int n , x , Ans;

bitset< 32 > temp;
vector< bitset< 32 > > A;

void solve() {
    read(n);
    for(int i = 1 ; i <= n ; i++ ) {
        read(x);
        temp = x;
        A.push_back(temp);
    }
    for(int i = 31 ; i >= 0 ; i-- ) {
        vector< bitset< 32 > > vec;
        for(int j = 0 ; j < A.size() ; j++ )
            if( A[ j ][ i ] ) vec.push_back( A[j] );
        if(vec.size() >= 2) A = vec;
        vec.clear();
    }
    temp = A[0] & A[1];
    writeln(temp.to_ulong());
}

int main() {
    solve();
    return 0;
}

Data

7mva - b5875c8e6f9e90bf4b7753e95c45fa14

make使用python+洛谷的cyaron写的,可以

pip install cyaron

发表评论

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