首页 > 代码库 > SGU 275 To xor or not to xor 高斯消元求N个数中选择任意数XORmax
SGU 275 To xor or not to xor 高斯消元求N个数中选择任意数XORmax
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
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_pairtypedef long long LL;const long long INF = 1e18;const double Pi = acos(-1.0);const int N = 1e3+10, M = 1e6, mod = 1e9+7, inf = 2e9;int n,a[66][N];int main() { scanf("%d",&n); for(int i = 0; i < n; ++i) { LL x;int cnt = 0; scanf("%I64d",&x); while(x) { a[cnt++][i] = x%2; x/=2; } } for(int i = 0; i < 63; ++i) a[i][n] = 1; LL ans = 0; for(int i = 62; i >= 0; --i) { int x = -1; for(int j = 0; j < n; ++j) { if(a[i][j]) { x = j;break; } } if(x == -1 && a[i][n] == 0) { ans += 1LL<<i; } else if(x != -1) { ans += 1LL<<i; for(int k = i - 1; k >=0; --k) { if(a[k][x]) { for(int j = 0; j <= n; ++j) a[k][j] ^= a[i][j]; } } } } cout<<ans<<endl; return 0;}
SGU 275 To xor or not to xor 高斯消元求N个数中选择任意数XORmax
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。