hdu4825 Xor Sum【Trie、Xor】

2019-11-06 07:12:49

字体：大中小

来源：转载

供稿：网友

题目：http://acm.hdu.edu.cn/showPRoblem.php?pid=4825

题意：

给一个数组（n个数，n<1e5），然后m个询问，给出一个x，给出数组中与x异或值最大的那个数？

分析：

给n个数建立字典树，如果异或值最大，那么就找两个数的二进制尽量不同。

代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N = 100000<<5;struct Trie { int a[2]; ll num;} f[N];int cnt;void insert(ll x,int num) { bool k; int u=0; for (int i = num; i >= 0; i--) { k = (1LL<<i)&x; if (f[u].a[k] == -1) f[u].a[k] = ++cnt; u = f[u].a[k]; } f[u].num = x;}ll query(ll x, int num) { bool k; int u=0; for (int i = num; i >= 0; i--) { k = (1LL<<i)&x; if (f[u].a[!k] != -1) u = f[u].a[!k]; else u = f[u].a[k]; } return f[u].num;}int main() { //freopen("in.txt","r",stdin); int n,m,T; ll x; scanf("%d",&T); for(int cas=1; cas<=T; cas++) { printf("Case #%d:/n",cas); memset(f, -1, sizeof(Trie) * N); scanf("%d%d", &n,&m); cnt = 0; for(int i=0; i<n; i++) { scanf("%lld", &x); insert(x,31); } for(int i=0; i<m; i++) { scanf("%lld",&x); printf("%lld/n",query(x,31)); } } return 0;}

上一篇：CodeForces - 724A

下一篇：node.js开发