ACM学习历程—SGU 275 To xor or not to xor(xor高斯消元)

时间:2021-07-11 02:32:32

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=275

这是一道xor高斯消元。

题目大意是给了n个数,然后任取几个数,让他们xor和最大。

首先根据题目意思可以列出下列方程组:

//a11x1+a21x2……=d[1]

//a12x1+a22x2……=d[2]

//...

(每个数二进制按列来写,xi为0或1,表示取或不取这个数。)

结果的二进制即为d数组。

由于需要结果最大,而结果最多是d全为1,那么就假设所有d均为1,然后进行高斯消元,来判断该行的d是否能取到。

步骤如下:

1、建立增广矩阵。

2、从最后一行往前扫,如果该行存在1,那么d[i]自然能取到1,这样需要把该列其它的1消掉,由于是高斯消元,消1的时候需要整行消;如果该行不存在1,而且d[i] == 0,自然该行的方程仍然有解。

3、消元的过程中保存答案。

复杂度O(63*63n)

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long long using namespace std; const int len = ;
int n, a[][];
bool vis[]; void xorGauss()
{
LL ans = ;
for (int i = len-; i >= ; i--)
{
int j;
for (j = ; j < n; j++)
{
if (a[i][j] && !vis[j])
{
vis[j] = true;
ans += (LL)<<i;
break;
}
}
if(j == n)
{
if(a[i][n] == )
ans += (LL)<<i;
}
else
{
for (int k = i-; k >= ; k--)
{
if (a[k][j])
{
for (int v = ; v <= n; v++)
a[k][v] ^= a[i][v];
}
}
}
}
printf("%I64d\n", ans);
} void input()
{
memset(a, , sizeof(a));
memset(vis, false, sizeof(vis));
//next is input
LL v;
int k;
for (int i = ; i < n; i++)
{
scanf("%I64d", &v);
for (int j = ; v > ; j++)
{
k = v&;
a[j][i] = k;
v >>= ;
}
}
//pre is input
for (int i = ; i < len; i++)
a[i][n] = ;
} int main()
{
// freopen("test.in", "r", stdin);
while (scanf("%d", &n) != EOF)
{
input();
xorGauss();
}
return ;
}

其实到这里这个问题并没有完美解决。

起始从前面的方程组可以看出来,一组矩阵,可以等同于另一组等价的矩阵。

于是我们只需要找出这个矩阵里面的最大线性无关组。(数之间不能互相表示)

然后通过线性无关组就能表示最大值了。

其实就是把矩阵化成最简矩阵。

然后这时把一个数看成整体,就能用位运算优化了。

效率O(63n)

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long long using namespace std; //xor高斯消元求线性基
//时间复杂度O(63n)
const int maxN = ;
int n;
LL a[maxN]; int xorGauss(int n)
{
int row = ;
for (int i = ; i >= ; i--)
{
int j;
for (j = row; j < n; j++)
if(a[j]&((LL)<<i))
break;
if (j != n)
{
swap(a[row], a[j]);
for (j = ; j < n; j++)
{
if(j == row) continue;
if(a[j]&((LL)<<i))
a[j] ^= a[row];
}
row++;
}
}
return row;
} void work()
{
for (int i = ; i < n; i++)
scanf("%I64d", &a[i]);
int row;
row = xorGauss(n);
LL ans = ;
for (int i = ; i < row; ++i)
ans = max(ans, ans^a[i]);
printf("%I64d\n", ans);
} int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d", &n) != EOF)
{
work();
}
return ;
}