【題解】HDU 4852 Xor Sum

【題目敘述】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";
        }
    }
}
分享本文 Share with friends