【題目敘述】https://vjudge.net/problem/HDU-4825
【解題想法】01 字典樹
#include <iostream>
using namespace std;
int Case, t, n, m, idx, a;
struct s{
int nxt[2];
}node[3200000];
void build(int x){
int cur = 1;
for (int i = 30; i >= 0; i--){
if (x & (1<<i)){
if (node[cur].nxt[1]) cur = node[cur].nxt[1];
else{
node[cur].nxt[1] = idx;
idx++;
cur = node[cur].nxt[1];
}
}
else {
if (node[cur].nxt[0]) cur = node[cur].nxt[0];
else{
node[cur].nxt[0] = idx;
idx++;
cur = node[cur].nxt[0];
}
}
}
}
int query(int x){
int cur = 1, target;
int ret = 0;
for (int i = 30; i >= 0; i--){
if (x & (1<<i)) target = 0;
else target = 1;
if (node[cur].nxt[target]){
if (target == 1) ret += (1<<i);
cur = node[cur].nxt[target];
}
else {
target ^= 1;
if (target == 1) ret += (1<<i);
cur = node[cur].nxt[target];
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--){
cin >> n >> m;
for (int i = 0; i < idx; i++){
node[i].nxt[0] = 0;
node[i].nxt[1] = 0;
}
idx = 2;
for (int i = 0; i < n; i++){
cin >> a;
build(a);
}
Case++;
cout << "Case #" << Case << ":\n";
for (int i = 0; i < m; i++){
cin >> a;
cout << query(a) << "\n";
}
}
}