SGU 275 To xor or not to xor 高斯消元求N个数中选择任意数XORmax

时间：2021-03-20 02:31:29

275. To xor or not to xor

 
The sequence of non-negative integers A1, A2, ..., AN is given. You are to find some subsequence Ai 1, Ai 2, ..., Ai k (1 <= i 1 < i 2 < ... < i k<= N) such, that Ai 1 XOR Ai 2 XOR ... XOR Ai k has a maximum value.
Input
The first line of the input file contains the integer number N (1 <= N <= 100). The second line contains the sequence A1, A2, ..., AN (0 <= Ai <= 10^18). 
Output
Write to the output file a single integer number -- the maximum possible value of Ai 1 XOR Ai 2 XOR ... XOR Ai k. 
Sample test(s)
Input
 
 
3 
11 9 5 
 
 
Output
 
 
14 
 题意：
　　从N个数中选择任意个数，求异或的最大值
题解：
　　从高位贪心
　　高斯消元判断能否构成1
　　复杂度 60*N*N
#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18;

const double Pi = acos(-1.0);

const int N = 1e3+, M = 1e6, mod = 1e9+, inf = 2e9;

int n,a[][N];

int main() {

    scanf("%d",&n);

    for(int i = ; i < n; ++i) {

        LL x;int cnt = ;

        scanf("%I64d",&x);

        while(x) {

            a[cnt++][i] = x%;

            x/=;

        }

    }

    for(int  i = ; i < ; ++i) a[i][n] = ;

    LL ans = ;

    for(int  i = ; i >= ; --i) {

        int x = -;

        for(int j = ; j < n; ++j) {

            if(a[i][j]) {

                x = j;break;

            }

        }

        if(x == - && a[i][n] == ) {

            ans += 1LL<<i;

        } else if(x != -) {

            ans += 1LL<<i;

            for(int k = i - ; k >=; --k) {

                if(a[k][x]) {

                    for(int j = ; j <= n; ++j) a[k][j] ^= a[i][j];

                }

            }

        }

    }

    cout<<ans<<endl;

    return ;

}
 

相关文章