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

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

 

 

题意:给你n个数,可以选择任意个数异或,但是要使得最后的异或值最大。

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

……

 

 

很好的题目、

SGU 275. To xor or not to xor (高斯消元法)
 1 /* ***********************************************
 2 Author        :kuangbin
 3 Created Time  :2014-1-31 0:48:47
 4 File Name     :E:\2014ACM\SGU\SGU275.cpp
 5 ************************************************ */
 6 
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <math.h>
17 #include <stdlib.h>
18 #include <time.h>
19 using namespace std;
20 
21 long long bit[100];
22 int a[100][110];
23 bool used[110];
24 
25 int main()
26 {
27     //freopen("in.txt","r",stdin);
28     //freopen("out.txt","w",stdout);
29     bit[0] = 1;
30     for(int i = 1;i < 63;i++)
31         bit[i] = 2*bit[i-1];
32     int n;
33     long long x;
34     while(scanf("%d",&n) == 1)
35     {
36         for(int i = 0;i < n;i++)
37         {
38             cin>>x;
39             for(int j = 0;j < 63;j++)
40             {
41                 if(x & bit[62-j])
42                     a[j][i] = 1;
43                 else a[j][i] = 0;
44             }
45         }
46         for(int i = 0;i < 63;i++)
47             a[i][n] = 1;
48         memset(used,false,sizeof(used));
49         long long ans = 0;
50         for(int i = 0;i < 63;i++)
51         {
52             int x = -1;
53             for(int j = 0;j < n;j++)
54                 if(a[i][j] && !used[j])
55                 {
56                     x = j;
57                     break;
58                 }
59             if(x == -1 && a[i][n] == 0)
60                 ans += bit[62-i];
61             else if(x != -1)
62             {
63                 ans += bit[62-i];
64                 for(int k = i+1; k < 63;k++)
65                     if(a[k][x])
66                     {
67                         for(int j = 0;j <= n;j++)
68                             a[k][j] ^= a[i][j];
69                     }
70             }
71         }
72         cout<<ans<<endl;
73     }
74     return 0;
75 }
SGU 275. To xor or not to xor (高斯消元法)

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

上一篇:Unity3D TouchScript 插件教程一


下一篇:转载:知行合一