AcWing 143. 最大異或對
【題目描述】

在查看解析之前，先給自己一點時間思考哦！

【題解】
本題要求給定一個整數序列，找出其中任意兩個數進行異或運算后，結果的最大值是多少。由于數據規模較大，我們不能簡單地通過兩層循環直接遍歷所有組合，這樣的時間復雜度會達到$O(n^2)$，超出了時間限制。
我們可以利用Trie樹來高效解決這個問題。通過使用前綴樹，我們能夠將每個整數拆分成二進制形式，按照其二進制位插入樹中，然后在查詢時可以通過比較來找到最大可能的異或值。

關鍵點：
異或性質：我們要最大化的是兩個數的異或值，而異或的性質決定了異或值越大，二者的對應位越不相同。因此，在查詢時，我們會盡量選擇不同的位進行匹配。
Trie 樹結構：每個節點代表一個二進制位（0 或 1）。從根節點開始，每個數按位插入，如果當前數的某一位是 1，那么它就沿著該位的路徑插入樹中。
查詢最大異或值：當我們要查詢一個數的最大異或值時，從當前數的二進制表示的每一位開始，盡量沿著與當前位不同的路徑走。

實現步驟：
將每個數的二進制位逐位插入到 Trie 樹中。
在插入每個數的同時，查詢當前數和 Trie 樹中已有數的最大異或值，并更新最大異或值。
【參考代碼】

#include <iostream>
using namespace std;// 最大節點數和最大Trie樹的容量
const int N = 1e5 + 10, M = 31 * N;  
// son[i][0/1] 表示節點 i 的左/右子節點，a 存儲輸入的數，idx 用來給每個節點編號
int son[M][2], a[N], idx;  // 插入一個數到 Trie 樹
void insert(int x) {int p = 0;// 從高位到低位插入數的二進制位for(int i = 30; i >= 0; i--) {int u = x >> i & 1;  // 獲取當前二進制位if(!son[p][u])  // 如果該路徑沒有節點，則創建新節點son[p][u] = ++idx;p = son[p][u];  // 移動到下一個節點}
}// 查詢當前數與樹中已有數的最大異或值
int query(int x) {int p = 0, res = 0;  // p 為當前節點，res 為當前異或結果// 從高位到低位查詢最大異或值for(int i = 30; i >= 0; i--) {int u = x >> i & 1;  // 獲取當前二進制位// 嘗試選擇與當前位不同的路徑，以得到更大的異或值if(son[p][!u]) {p = son[p][!u];res = res * 2 + !u;} else {p = son[p][u];res = res * 2 + u;}}return res; 
}int main() {int n;cin >> n;  for(int i = 0; i < n; i++)cin >> a[i];  int res = 0;  // 用來存儲最大異或值for(int i = 0; i < n; i++) {insert(a[i]);  // 將當前數插入到 Trie 樹int t = query(a[i]);  // 查詢當前數的最大異或值res = max(res, a[i] ^ t);  // 更新最大異或值}cout << res << endl;  return 0;
}