HDU 3949 XOR（高斯消元搞基）

本文主要是介绍HDU 3949 XOR（高斯消元搞基），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU 3949 XOR

题目链接

题意：给定一些数字，问任取几个异或值第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;
}

这篇关于HDU 3949 XOR（高斯消元搞基）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---