The sequence of non-negative integers A1, A2, …, AN is given. You are to find some subsequence Ai1, Ai2, …, Aik (1 <= i1 < i2 < … < ik <= N) such, that Ai1 XOR Ai2 XOR … XOR Aik has a maximum value.
The first line of the input file contains the integer number N (1 <= N <= 100). The second line contains the sequence A1, A2, …, AN (0 <= Ai <= 10^18).
Output
Write to the output file a single integer number — the maximum possible value of Ai1 XOR Ai2 XOR … XOR Aik.
3
11 9 5
Sample Output
14
Meaning
题目就是问你有n个数，从中选出若干个xor起来最大是多少。
Solution
一道有意思的题目。
网上看到的很多题解，很多都含糊其辞，其实这道题并不难。我们把每个数写成二进制竖着摞起来，就变成了一个矩阵，我们只要把这个矩阵旋转九十度就可以得到高斯消元的矩阵了。
对于将结果列置为真，我是这样理解的：先假设他为1，如果成立，则为1，否则为0，类似于假设法。变元为第i个数选还是不选。
对于每一行，如果这一行有一个没有用过的变量，这行一定对答案贡献1«k，其他有种情况，就是这行一个可用变量都没有，可是结果列为0，这种情况对答案贡献也是1«k，因为这相当于说一大堆0 and 起来等不等于0。显然为真。
搞搞就能A了。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <cstdio>
typedef long long ll;
ll getll() {
ll r = 0; char c = getchar();
for (; c < '0' || c > '9'; c = getchar());
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r;
}
int n, matrix[70][110], maxlen = 0;
ll ans;
bool used[110];
void init() {
ll a;
n = getll();
for (int i = 0; i < n; ++i) {
a = getll();
int j;
for (j = 0; a; ++j, a >>= 1) {
if (a & 1) matrix[j][i] = 1;
else matrix[j][i] = 0;
}
if (maxlen < j) maxlen = j;
}
for (int i = 0; i < maxlen; ++i) matrix[i][n] = 1;
}
void work() {
ans = 0;
for (int i = 0; i < n; ++i) used[i] = false;
for (int i = maxlen-1; i >=0; --i) {
ans <<= 1;
int j = 0;
for (; j < n; ++j) {
if (matrix[i][j] && !used[j]) {
used[j] = true;
ans |= 1;
break;
}
}
if (j == n) { if (matrix[i][n] == 0) ans |= 1; }
else { for (int k = i-1; k >= 0; --k) if (matrix[k][j]) for (int l = 0; l <= n; ++l) matrix[k][l] ^= matrix[i][l]; }
}
}
int main () {
init();
work();
printf("%lld", ans);
return 0;
}
|