sgu275 To xor or not to xor ----高斯消元复习
275. To xor or not to xor time limit per test: 0.5 sec.
memory limit per test: 65536 KBinput: standard
output: standard
The sequence of non-negative integers A1, A2, ..., AN is given. You are to find some subsequence Ai1, Ai2, ..., Aik (1 <= i1 < i2 < ... < ik <= N) such, that Ai1 XOR Ai2 XOR ... XOR Aik has a maximum value.
InputThe 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).
OutputWrite to the output file a single integer number -- the maximum possible value of Ai1 XOR Ai2 XOR ... XOR Aik.
Sample test(s)
Input
Output14 [submit][forum]
真是一道好题，不是真正理解高斯消元是无法做这题的。
题意：给你n个数，可以选择任意个数异或，但是要使得最后的异或值最大。
我们把每个数用二进制表示，要使得最后的异或值最大，就是要让高位尽量为1，高位能不能为1就必须用高斯消元判断了。
1. 根据数的二进制表示，建立方程组的矩阵，结果那列置为1。
2. 从下往上高斯消元(高位放下面)，如果该行有未被控制的变元，则该行的结果一定为1，且该变元控制该行。
3. 从该行往上依次消掉(异或)该变元。
4. 如果该行没有可以用来控制的变元，如果最后一列是0，则该行结果也为1，否则该行结果为0。这里能抱着已用来控制的变元的系数全是0，因为在第3步时就消掉该行以上此列的0了，后面0与0以后还是0。所以如果最后一列是0, 即该行方程也可以成立，故结果为1。
建立方程：
a11x1+a21x2……=d[1]
a12x1+a22x2……=d[2]
……
#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>#define ll long longusing namespace std;int equ,var;int n;int a[62][105];bool vis[105];void gauss(){ ll ans=0; int i,j,k; for(i=equ-1;i>=0;i--) { ans<<=1; for(j=0;j<var;j++) { if(a[i][j]&&!vis[j]) { vis[j]=true; ans|=1; break; } } if(j==var) { if(a[i][var]==0) ans|=1; } else { for(k=i-1;k>=0;k--) { if(a[k][j]) { for(int l=0;l<var+1;l++) a[k][l]^=a[i][l]; } } } } // cout<<equ<<" "<<var<<"*"<<endl; cout<<ans<<endl;}void init(){ ll m; var=n;//n个数，所以n个未知数 equ=0; int k; for(int i=0;i<n;i++) { cin>>m; k=0; while(m!=0) { int j=m&1; a[k++][i]=j;m>>=1; } if(k>equ) equ=k; } for(int i=0;i<equ;i++) a[i][var]=1;}int main(){ while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof(a)); memset(vis,false,sizeof(vis)); init(); gauss(); }}