# [AcWing143] 最大异或和 [字典树]

2021-01-15 21:14

阅读：392

标签：存在 cpp mem query include can ++i inline code

[AcWing143] 最大异或和 [字典树]

传送门

题意

给出N个整数，选择两个整数，使得异或和最大（\(0）

思路

从数据范围很容易想到二进制，进而想到字典树Trie。

字典树的典型应用是存储字符串，存储二进制也是一样的。

我一开始在处理取二进制位的时候想的比较麻烦，我是使用右移运算符先预处理出每个数的二进制表示，再根据二进制表示插入字典树中。后来了解到x >> i & 1;可以直接取二进制数的任意一位，这样简单了许多。

查询的时候，先取出对应位的二进制数，在树中先走该二进制数的对立面，如果对立面不存在，再沿着该二进制数向下走一层。

Code：

#include 
using namespace std;
#define fre freopen("data.in","r",stdin);
#define ms(a) memset((a),0,sizeof(a))
#define go(i,a,b) for(register int (i)=(a);(i)=0;i--){
        t= x >> i & 1; //取二进制数的第i位，从0开始
        if(!son[p][t])son[p][t]=++idx;
        p=son[p][t];
    }
}
inline int query(int x){
    int ans=0,t,p=0;
    for(int i=30;i>=0;--i){
        t=x>>i&1;
        if(son[p][!t]){
            p=son[p][!t];
            ans|=(1

# [AcWing143] 最大异或和 [字典树]

标签：存在 cpp mem query include can ++i inline code

原文地址：https://www.cnblogs.com/sstealer/p/12233116.html

上一篇：AcWing842 排列数字

下一篇：C# Dictionary 的几种遍历方法转

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：# [AcWing143] 最大异或和 [字典树]
文章链接：http://soscw.com/index.php/essay/42417.html

亲，登录后才可以留言！

# [AcWing143] 最大异或和 [字典树]

[AcWing143] 最大异或和 [字典树]

题意

思路

评论

热门文章

推荐文章

最新文章

置顶文章