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

时间:2022-06-21 11:33:00

题目链接

题意:有n个数,范围是[0, 10^18],n最大为100,找出若干个数使它们异或的值最大并输出这个最大值。

分析:

一道高斯消元的好题/

我们把每个数用二进制表示,要使得最后的异或值最大,就是要让高位尽量为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]

。。。

还有一个写的比较好的博客:http://blog.csdn.net/ivan_zjj/article/details/7629055

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define LL __int64
const int maxn = +;
using namespace std;
int a[maxn][maxn], vis[maxn];
LL b[maxn]; int main()
{
LL ans, x;
int n, i, j, k;
b[] = ;
for(i = ; i < ; i++)
b[i] = *b[i-];
while(~scanf("%d", &n))
{
ans = ;
memset(vis, , sizeof(vis));
for(i = ; i < n; i++)
{
scanf("%I64d", &x);
for(j = ; j < ; j++)
if(x & b[-j])
a[j][i] = ;
else
a[j][i] = ;
}
for(i = ; i < ; i++)
a[i][n] = ;
for(i = ; i < ; i++)
{
int tmp = -;
for(j = ; j < n; j++)
if(a[i][j] && !vis[j])
{
tmp = j;
break;
}
if(tmp==- && a[i][n]==)
ans += b[-i];
else if(tmp!=-)
{
ans += b[-i];
for(k = i+; k < ; k++)
if(a[k][tmp])
{
for(j = ; j <= n; j++)
a[k][j] ^= a[i][j];
}
}
}
printf("%I64d\n", ans);
}
return ;
}