题解0014：信奥一本通1472——The XOR Largest Pair（字典树）

题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1472

题目描述：在给定的 N 个整数中选出两个进行异或运算，求得到的结果最大是多少。

看到这道题要搞异或，首先想到把它们转成二进制。

那用什么存呢？

这就要用到一个比较NB的算法——字典树了。

（对字典树不太了解的可以先看我另一篇博客——https://www.cnblogs.com/wdrdsahudhisjabshdahuhsh/p/16323517.html）

这就是把一堆整数转成2进制数，再存到字典树里，并用字典树查找最大结果。

（ps：异或就是二进制中当两个值不相同时返回1，否则返回0）

上代码（有注释）：

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int a,trie[4000001][2],tot=0;

 4 void in(int a){//转成二进制并存入字典树

 5     int root=0,id;

 6     for(int i=30;i>=0;i--){//从最高位开始

 7         id=(a>>i)&1;//提取a在二进制中第i位的值

 8         if(trie[root][id]==0){

 9             trie[root][id]=++tot;

10         }

11         root=trie[root][id];//字典树

12     }

13 }

14 int out(int a){

15     int root=0,id,ans=0;

16     for(int i=30;i>=0;i--){

17         id=(a>>i)&1;

18         if(trie[root][!id]){//找到不同的值了

19             ans=ans|(1<<i);//加上异或这一位的值

20             root=trie[root][!id];//换节点继续查

21         }else{

22             root=trie[root][id];//直接往下走

23         }

24     }

25     return ans;

26 }

27 int main(){

28     int n,ans=0;

29     cin>>n;

30     while(n--){

31         cin>>a;

32         in(a);

33         ans=max(ans,out(a));//求最大值

34     }

35     cout<<ans;//完事

36 }

巴特西

题解0014：信奥一本通1472——The XOR Largest Pair（字典树）

最新文章

热门文章