HDU 3949 XOR（高斯消元搞基）

HDU 3949 XOR

題目鏈接

題意：給定一些數字，問任取幾個異或值第k大的

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

代碼：

#include 
#include 
#include 
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;
}