U109895 [HDU4825]Xor Sum
这道题目
样例都过了,但是不知道为什么wa了
#include<bits/stdc++.h>
#define int long long
using namespace std;
int tempch[55];
int tot, root;
struct node{
int ch[2];
int cnt;
void init() {
ch[0] = ch[1] = 0;
cnt = 0;
}
}trie[5001000];
void insert() {
int p = root;
for(int i=0; i<=31; ++i) {
if(!trie[p].ch[tempch[i]]) {
trie[p].ch[tempch[i]] = ++tot;
}
p = trie[p].ch[tempch[i]];
trie[p].cnt ++;
}
}
int ask() {
int ans = 0;
int p = root;
for(int i=0; i<=31; ++i) {
if(trie[p].ch[!tempch[i]] == 0) {
p = trie[p].ch[tempch[i]];
if(tempch[i] == 1) {
ans += (1<<(31-i));
}
} else {
p = trie[p].ch[!tempch[i]];
if(tempch[i] == 0) {
ans += (1<<(31-i));
}
}
}
return ans;
}
signed main() {
root = ++tot;
int n, m; cin >> n >> m;
for(int i=1; i<=n; ++i) {
int temp; cin >> temp;
for(int j=0; j<=31; ++j) {
if(temp & (1ll<<(31ll-j))) {
tempch[j] = 1;
} else {
tempch[j] = 0;
}
}
// for(int j=0; j<=31; ++j) {
// cout << tempch[j] << " ";
// }
// cout << endl;
insert();
}
for(int i=1; i<=m; ++i) {
int temp; cin >> temp;
for(int j=0; j<=31; ++j) {
if(temp & (1<<(31ll-j))) {
tempch[j] = 1;
} else {
tempch[j] = 0;
}
}
// for(int j=0; j<=31; ++j) {
// cout << tempch[j] << " ";
// }
// cout << endl;
cout << ask() << endl;
}
return 0;
}