SGU 275 To xor or not to xor (高斯消元)

题目地址：SGU 275

首先，贪心的思想，每一二进制位上要尽量是1，而能不能是1用高斯消元来解决。当该位有一个可以使之为1的变元时，就说明这位可以为1，而且令该变元控制该位，然后向低位消元。

代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=1e9;
const double eqs=1e-9;
int mat[100][110], equ, var, vis[110];
LL a[100];
LL gauss()
{
        LL ans=0;
        int i, j, k, h;
        memset(vis,0,sizeof(vis));
        for(i=equ-1;i>=0;i--){
                ans<<=1;
                for(j=0;j<var;j++){
                        if(mat[i][j]&&!vis[j]){
                                vis[j]=1;
                                ans|=1;
                                break;
                        }
                }
                if(j==var){
                        if(mat[i][var]==0) ans|=1;
                }
                else{
                        for(k=i-1;k>=0;k--){
                                if(mat[k][j]){
                                        for(h=0;h<=var;h++){
                                                mat[k][h]^=mat[i][h];
                                        }
                                }
                        }
                }
        }
        return ans;
}
int main()
{
        int n, i, k;
        LL y;
        scanf("%d",&n);
        equ=0;
        var=n;
        for(i=0;i<n;i++){
                scanf("%I64d",&a[i]);
        }
        memset(mat,0,sizeof(mat));
        for(i=0;i<n;i++){
                y=a[i];
                k=0;
                while(y){
                        mat[k++][i]=(y&1);
                        y>>=1;
                }
                equ=max(equ,k);
        }
        for(i=0;i<equ;i++){
                mat[i][var]=1;
        }
        printf("%I64d\n",gauss());
        return 0;
}

SGU 275 To xor or not to xor (高斯消元)

原文：http://blog.csdn.net/scf0920/article/details/43278525