HDU4825_01辞書ツリー

01ディクショナリ・ツリーは、通常のディクショナリ・ツリーの変形であり、主に2つの数の最大異または値の問題を処理するために使用されます.
まず、普通の辞書の木を01辞書の木にする方法を自分で考えてみましょう.

一般辞書ツリーに格納文字、例えば26文字の辞書ツリーが26フォークツリー、01辞書ツリーが01、明らかに二フォークツリー

である.

int型を格納01ディクショナリツリーは最大32層(第1層が通常のディクショナリツリーに類似してルートノードであり、何も格納されていない)

である.

01ディクショナリツリーは、実は整数データをバイナリに変換し、数のリーフノードはバイナリの最低ビットを格納し、ルートノードに近づくほど格納ビット数が高くなる.

最大の異或を解決するには、対応するビットの異なる分岐を貪欲に探せばいい.
例題HDU 4825はあなたにn個の数をあげて、更にm回の問い合わせを与えて、毎回尋ねることに対して、1つの値xを与えて、あなたにn個の数の中で1つの数を探し当てて、xと異なってあるいは値が最大です
では、まずn個の数に木を建てて、尋ねるたびに貪欲に探せばいいのです.
tips:ツリー削除操作については、すべての配列を直接初期化することと、ルートノードのみを初期化することと、2回目の作成中に初期化することと、ツリー削除操作の頻度を選択することができます.
ACコード:

#include 
using namespace std;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define ll long long

ll z_o_trie[32000000][2];
ll value[32000000];
ll cnt = 1;

void Insert(ll a)
{
    ll p = 0;
    for (ll i = 31; i >= 0; i--)
    {
        ll temp = (a >> i) & 1;
        if (z_o_trie[p][temp])
            p = z_o_trie[p][temp];
        else
            p = z_o_trie[p][temp] = cnt++;
    }
    value[p] = a;
}

ll get(ll a)
{
    ll p = 0;
    for (ll i = 31; i >= 0; i--)
    {
        ll temp = (a >> i) & 1;
        if (z_o_trie[p][temp ^ 1])
            p = z_o_trie[p][temp ^ 1];
        else
            p = z_o_trie[p][temp];
    }
    return value[p];
}
void init()
{
    cnt = 1;
    fill(z_o_trie[0], z_o_trie[0] + 1000000 * 2, 0);
    fill(value, value + 1000000, 0);
}
int main()
{
    IOS;
    ll t;
    cin >> t;
    ll CASE = 1;
    while (t--)
    {
        cout << "Case #" << CASE++ << ":" << endl;
        init();
        ll n, m;
        cin >> n >> m;
        for (ll i = 1; i <= n; i++)
        {
            ll temp;
            cin >> temp;
            Insert(temp);
        }
        for (ll i = 1; i <= m; i++)
        {
            ll temp;
            cin >> temp;
            cout << get(temp) << endl;
        }
    }
    return 0;
}