正題

題目鏈接:https://loj.ac/problem/10050

---

題目大意

有n個(gè)數(shù)，求兩個(gè)數(shù)使他們異或起來(lái)最大。

---

解題思路

我們考慮構(gòu)建一個(gè)TrieTrie。
兩個(gè)分叉為0,1，對(duì)于每個(gè)數(shù)二進(jìn)制下不夠30位我們將其補(bǔ)夠30位，然后再根據(jù)二進(jìn)制01構(gòu)建TrieTrie。
然后我們?cè)俅蚊杜e一邊，然后依舊是補(bǔ)位轉(zhuǎn)二進(jìn)制，然后每次盡量走反方向的邊，在路上統(tǒng)計(jì)一下，取最小值就是答案。

---

code

#include<cstdio> #include<algorithm> #define N 100010 using namespace std; int n,l[N*40][2],x,tot,a[N]; int maxs; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);int now=0;for(int j=30;j>=0;j--)//構(gòu)建{x=(a[i]>>j)&1;if(!l[now][x]) l[now][x]=++tot;now=l[now][x];}}for(int i=1;i<=n;i++){int now=0;int ans=0;for(int j=30;j>=0;j--)//查詢(xún){x=((a[i]>>j)&1)^1;//反位if(!l[now][x]) now=l[now][x^1];else{ans+=1<<j;now=l[now][x];}}maxs=max(maxs,ans);}printf("%d",maxs); }

總結(jié)

以上是生活随笔為你收集整理的loj#10050-The XOR Largest Pair【Trie(字典树)】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。