SGU 275 To xor or not to xor （高斯消元）

题意：有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 ;

 }

巴特西

SGU 275 To xor or not to xor （高斯消元）

最新文章

热门文章