HDU 3949 XOR

pid=3949″ target=”_blank” style=””>题目链接

题意：给定一些数字，问任取几个异或值第k大的

思路：高斯消元搞基，然后从低位外高位去推算

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long ll;
const int N = 10005;int t, n;
ll a[N];void gauss() {
int r = 0;
for (int i = 60; i >= 0; i--) {
int j;
for (j = r; j < n; j++)
if ((a[j]>>i)&1)
break;
if (j == n) continue;
swap(a[j], a[r]);
for (int k = 0; k < n; k++)
if (k != r && ((a[k]>>i)&1))
a[k] ^= a[r];
r++;
}
sort(a, a + n);
n = unique(a, a + n) - a;
}ll cal(ll k) {
int i = 0;
if (a[0] == 0) {
i++;
if (k == 1) return 0;
k--;
}
ll ans = 0;
for (; i < n && k; i++) {
if (k&1) ans ^= a[i];
k >>= 1;
}
if (i == n && k) return -1;
return ans;
}int main() {
int cas = 0;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%I64d", &a[i]);
gauss();
int q;
scanf("%d", &q);
ll k;
printf("Case #%d:\n", ++cas);
while (q--) {
scanf("%I64d", &k);
printf("%I64d\n", cal(k));
}
}
return 0;
}