SGU 275 To xor or not to xor【最大xor和高斯消元】

题目大意：给你n个数（n<=100）要你找出若干个数使他们的异或和最大

思路：高斯-若当消元消完以后削成若干个独立的行向量，将它们异或起来就好

#include<cstdio>

#include<string.h>

#include<iostream>

#include<algorithm>

#define maxn 3000

#define LL __int64

using namespace std;

LL bin[maxn],a[maxn];

int main()

{

int n;

scanf("%d",&n);

for(int i=1;i<=n;i++)scanf("%I64d",&a[i]);

for(int i=1;i<=61;i++)bin[i]=(1ll<<(i-1));

int now=0;

for(int i=61;i>=1;i--)

{

int idx=now+1;

while((a[idx]&bin[i])==0 && idx<=n)idx++;

if(idx==n+1)continue;

swap(a[idx],a[now+1]);

now++;

for(int j=1;j<=n;j++)if((a[j]&bin[i])!=0 && now!=j)a[j]^=a[now];

}

LL ans=0;

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

printf("%I64d\n",ans);

return 0;

}

巴特西