洛谷 P10471 最大异或对 The XOR Largest Pair

// P10471 最大异或对 —— 正解：01-Trie ＋ 从高位往低位贪心，O(31 N)
//
// ★ 这就是[第 50 章第 11 步](/ch/50-trie/)那道小题的原题，一个字都没改：
//   **把一个整数看成一个长度固定的「01 字符串」**（从第 30 位写到第 0 位），
//   于是「找一个和 x 异或最大的数」就是「在 Trie 上顺着**每一位都尽量走反面**」。
//
// ⚠⚠ 两处会咬人的地方，都不在 Trie 上：
//   ① **多少位**：题面写 `0 ≤ Aᵢ < 2³¹` ⇒ 最高位是第 **30** 位，一共 **31** 位。
//      写成 30 位（第 29 位起）就把最高位整个丢了 —— 而随机小数据一个字都不会错。
//   ② 贪心的每一步**必须先看反面那条边在不在**，不在就只能走本侧 ——
//      少了这一句，`u` 会掉到 0 号节点（根）上去，后面的位全在读别人的家底。
//
// ★ 而「边插边查」还是「先全插完再查」这件事，看着像个坑，其实**一次都不会错** ——
//   理由和自检写在解析页第 ⑤ 步。

#include <bits/stdc++.h>
using namespace std;

const int BITS = 31;                    // ★ 0 ≤ Aᵢ < 2³¹ ⇒ 第 30 位到第 0 位，一共 31 位
const int MAXN = 100005 * BITS + 5;     // 每个数最多新开 31 个节点

int ch[MAXN][2];
int tot;

void insertNum(int x) {
    int u = 0;
    for (int b = BITS - 1; b >= 0; b--) {
        int k = (x >> b) & 1;
        if (!ch[u][k]) ch[u][k] = ++tot;
        u = ch[u][k];
    }
}

/** 树里已经有的数当中，和 x 异或最大的那个异或值 */
int askMax(int x) {
    int u = 0, res = 0;
    for (int b = BITS - 1; b >= 0; b--) {
        int k = (x >> b) & 1;
        if (ch[u][k ^ 1]) { res |= 1 << b; u = ch[u][k ^ 1]; }   // ⚠ 先看反面在不在
        else u = ch[u][k];
        if (!u) break;                                           // 树是空的（只有第一个数会走到这儿）
    }
    return res;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x;
        if (scanf("%d", &x) != 1) return 0;
        if (i) ans = max(ans, askMax(x));      // ★ 边插边查 ⇒ 天然只和「前面的数」配对
        insertNum(x);
    }
    printf("%d\n", ans);
    return 0;
}

// P10471 的三笔账：节点数 / 内存、两条路各做多少次基本动作、以及那个「精确的 0」的自检
//
// 用法：./p10471Count <csv|table> < 一份输入
//
// ★ 第三件事最要紧：p10471Self（先把 N 个数全插完再逐个查询）**一次都不会错**，
//   而「一个反例都没有」和「这段代码根本没在跑」输出上一模一样
//   （[第 19 章 P2240](/sol/p2240/) 那条规矩）。
//   ⇒ 所以这一份顺手把**同一处改动**放到另一个问题上验一遍：
//     求「最**小**异或对」时，自己配自己就是 0，那时候它当场全错。

#include <bits/stdc++.h>
using namespace std;

const int BITS = 31;

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";

    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) if (scanf("%d", &a[i]) != 1) return 0;

    /* ① Trie 的节点数（= 所有数的不同「二进制前缀」个数）—— 排序之后数相邻的 LCP 就行 */
    long long nodes = 0;
    {
        vector<int> v(a);
        sort(v.begin(), v.end());
        long long prevLen = -1;
        int prev = 0;
        for (size_t i = 0; i < v.size(); i++) {
            if (i == 0) { nodes += BITS; prev = v[0]; prevLen = BITS; continue; }
            int d = prev ^ v[i];
            int common = BITS;                       // 和上一个数共用多少位高位前缀
            for (int b = BITS - 1; b >= 0; b--) if ((d >> b) & 1) { common = BITS - 1 - b; break; }
            nodes += BITS - common;
            prev = v[i];
            (void)prevLen;
        }
    }

    /* ② 两条路各做多少次基本动作 */
    long long brutePairs = (long long)n * (n - 1) / 2;
    long long trieSteps = (long long)n * BITS * 2;   // 每个数插一遍 + 查一遍，各 31 步

    /* ③ ★ 那个「精确的 0」的自检：最大 vs 最小，各算「允许自己配自己」和「不允许」两种 */
    int maxNo = 0, maxYes = 0;
    int minNo = INT_MAX, minYes = INT_MAX;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int v = a[i] ^ a[j];
            if (i != j) { maxNo = max(maxNo, v); minNo = min(minNo, v); }
            maxYes = max(maxYes, v);
            minYes = min(minYes, v);
        }

    vector<pair<string, long long> > out;
    out.push_back(make_pair("n", n));
    out.push_back(make_pair("nodes", nodes));
    out.push_back(make_pair("mib_x100", (long long)(nodes * 2 * 4 * 100.0 / 1048576.0)));
    out.push_back(make_pair("brute_pairs", brutePairs));
    out.push_back(make_pair("trie_steps", trieSteps));
    out.push_back(make_pair("ratio", trieSteps ? brutePairs / trieSteps : 0));
    out.push_back(make_pair("max_no", maxNo));
    out.push_back(make_pair("max_yes", maxYes));
    out.push_back(make_pair("max_same", maxNo == maxYes ? 1 : 0));
    out.push_back(make_pair("min_no", minNo));
    out.push_back(make_pair("min_yes", minYes));
    out.push_back(make_pair("min_same", minNo == minYes ? 1 : 0));

    if (mode == "csv") for (size_t i = 0; i < out.size(); i++) printf("%s,%lld\n", out[i].first.c_str(), out[i].second);
    else for (size_t i = 0; i < out.size(); i++) printf("  %-14s %lld\n", out[i].first.c_str(), out[i].second);
    return 0;
}