前言

$\%\%\%$北大爺的題目

---

正題

題目鏈接:https://www.luogu.com.cn/problem/U102380

---

題目大意

$n$個數，求一個數$k$使得$max\{a_{i}xork\}$最小。

---

解題思路

我們對每一個數按位建到一個$Trie$里，然后對于每個節點。

如果沒有子節點，證明是最下面的點，不管

如果有一個子節點，那么就直接異或為0，往下走

如果有兩個字節點，那么證明這兩個之中必定有一個要加上$2^k$，那么我們選擇小的那個即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; int n,t[N*30][2],cnt,root; int insert(int val){int x=root;for(int i=29;i>=0;i--){int w=(val>>i)&1;if(!t[x][w]) t[x][w]=++cnt;x=t[x][w];} } int dfs(int x,int k){if(!t[x][0]&&!t[x][1]) return 0;if(!t[x][0]) return dfs(t[x][1],k-1);if(!t[x][1]) return dfs(t[x][0],k-1);return (min(dfs(t[x][0],k-1),dfs(t[x][1],k-1))|(1<<k)); } int main() {scanf("%d",&n);root=cnt=1;for(int i=1;i<=n;i++){int x;scanf("%d",&x);insert(x);}printf("%d",dfs(1,29)); }

總結

以上是生活随笔為你收集整理的U102380-简单数据结构题【Trie】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。