进制转换该复习了
https://blog.csdn.net/m0_74215326/article/details/128930846?spm=1001.2014.3001.5502

这道题建树的关键是考虑了前导0

嘉人们 这写的太棒了捏

大佬们，为什么res=res2+1;这么写就算异或后， res=res2+!u;这么写就是没有异或呢？

因为他记录的是异或后的答案，你这个记的是要与数组里进行异或的最大解

if内的判断成功就相当于异或成功就可以把答案res左移加一

因为最后一个一定是1

问这问题代表没理解

破防了，我也不理解

###高数大佬

if(son[p][!u]) ////如果当前层有对应的不相同的数
        {   ///p指针就指到不同数的地址

          p=son[p][!u];
          res=res*2+1;
             ///*2相当左移一位  然后如果找到对应位上不同的数res+1 例如    001
        }                                                       ///       010 
        else                                            ////          --->011                                                                           //刚开始找0的时候是一样的所以+0    到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
        {
            p=son[p][u];
            res=res*2+0;
        }

这一段不太理解，qaq

res 是用来记录和当前 x 异或后结果的最大值

牛逼 看这个突然看懂了

为什么在main函数里没有初始化idx会行不通？

main里的变量是不默认初始化为0的，全局变量才会默认初始化为0

为什么高位向低位存储，不能从第一位向第31位存呢

因为是找到最大异或数，当然是从高位开始找，

但是从高位开始和从低位开始不是一样的嘛。
因为把每个数值插进去之后，整个树就固定了，然后找A的最大异或对。
A是固定的，整个树也是固定的，那最后答案不是一样的嘛

从最高位向最低位存储，这样在search过程中就可以知道
一个数存在不同的数的最高位是哪一位，而这样才能计算出
最后的res值。
例：27:00011011
7:00000111
这两个数中 存在不同的数的最高位是第5位则：
第五位(不同)：res=res2+1(res=1)
第四位(不同):res=res2+1(res=3)
第三位（不同）：res=res2+1(res=7)
第二位（相同）：res=res2(res=14)
第一位（相同）：res=res*2(res=28)
即这两个数异或的最终结果为28

我觉得主要是高位向低位存储可与直接使用i来代替第k位，方便进行位运算

为什么改为ｉｄｘ＋＋就错误了呢，而且　＋＋　ｉｄ那句有大佬可以解释一下怎么开辟的空间吗

idx初值为0，改成idx++第一个就会被赋值0，因为son = 0代表这个节点还没有，影响了判断

idx是son[p][u]的地址吗

肯定要先++啊，不然你执行完一次操作后idx还是0，而规定除了根节点其他节点下标不能为0

还不理解这道题的朋友们可以参考下这篇：https://blog.csdn.net/raelum/article/details/128885107

res=res*2+1的本质是让res字符串的第i位变成1，因为这个时候满足数x的第i位与当前层的数不一样，相异

理解了，大佬牛逼

确实，但是这种写法可读性并不高。至少等到遍历完那个1才移到第i位hhh

#include <iostream>

using namespace std;

const int N = 1e5 + 10, M = 31e5 + 10; //每个数转换为二进制最多有31位

int n;
int a[N], son[M][2], idx;

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];
    }
    //长度都一样就不用cnt数组标记最后一位了
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--)
    {
        int u = x >> i & 1;
        if (son[p][!u]) //取不同的数异或结果最大
        {
            p = son[p][!u];
            res = res * 2 + 1; //异或的结果  左移1位再+1
        }
        else //如果不存在
        {
            p = son[p][u];
            res = res * 2 + 0;
        }
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        insert(a[i]);
        res = max(res, search(a[i]));
    }

    printf("%d", res);

    return 0;
}

不明白为什么定义 son[N * 31] [2] , 不应该定义为son[31][2]就够了嘛

31只是一个数对应的二进制位数，但是题目有N个数啊，你这样怎么把这N个数存下来？

我也想不明白，不可以理解为31个节点，每个节点有0与1两种状态吗？这样就可以表示任意个数了

你想说的是son[31][2]是吧，其实不止31个节点，因为吗，每一个二进制位都有放 0 或者放 1 两种选择，31位最多会有 $2^{31}$ 中选择，所以说最多会有 $2^{31}$ 个节点。题目说有 $N$ 个数，我们就假定这些数的对应的二进制位都是不同的，那么最坏情况下会有 $31N$ 个节点，所以说开这么大是保底的，够用的。

你可以试试几个例子，把代码中的 $idx$ 输出到控制台看看，样例一就已经有有34个节点了。

懂了，谢谢大佬

建议看这个题解

[31][2]总共是31*2=62个，不是2^31个哦。

恍然大悟

为什么search()函数里这样写 res = res<<1 + 1，就是错的呢？输出一直是0，但换成res*2+1就没问题了，按道理来讲两者不是等价的吗？

<<的优先级比+要小

改成res = res << 1 | 1就可以了

感谢！

| 1 这里是怎么理解的，没太明白？结果是res<<1？

这是运算符优先级的问题，你要先乘除再加减最后位运算，<<和|都是位运算，就不存在+先算的问题了。
当然，你也可以写res=(res<<1)+1

明白了，非常感谢！

问一下各位大佬，res为什么要左移呀

更新res的值，每次把旧值乘以2（这一步相当于左移一位）再加上当前值。
比如给你一个字符串类型的二进制数str，让你转化成10进制数，就可以用下面这段代码实现

int res = 0;
for(int i = 0; i < str.size(); i ++) 
{
    res = res * 2 + (str[i] - '0');
    //也可以写成 res = res << 1 + (str[i] - '0');
}

感谢！

我想问一下如果在查询的时候同层没有，并且之前也没有这个数，那不是就会回到0了吗？

我的理解，在查询的时候一定会把所有的数位沿字典树最优路径（也就是找异或位）遍历完，得到的数就是最大异或数。所以不存在之前没有这个数，最后回到0的情况。Y总的视频里有点问题，应该是先把所有数都按字典树插入，然后再查询。

查询的时候不是判断son[p][!u]吗，如果这个值没有呢，他会去找son[p][u]，万一这个值也没有，p就为0了，怎么知道这两个值一定被idx扫过呢

兄弟你懂了吗我也困在这了

我可以讲一讲

这是我的代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1E5 + 10, M = 32;

int trie[N * M][2], tot = 1;
int a[N];
int n;
int ans;

void insert(int x)
{
    int p = 1;
    for (int i = 31; i >= 0; i -- )
    {
        int u = x >> i & 1;
        if (trie[p][u] == 0) trie[p][u] = ++ tot;
        p = trie[p][u];
    }
}

int query(int x)
{
    int p = 1, res = 0; 
    for (int i = 31; i >= 0; i -- )
    {
        int u = x >> i & 1;
        if (trie[p][!u]) 
        {
            p = trie[p][!u];
            res = (res << 1) + 1;
        }
        else if(trie[p][u])
        {
            p = trie[p][u];
            res = (res << 1) + 0;
        }
    }
    return res;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) insert(a[i]);
    for (int i = 1; i <= n; i ++ ) ans = max(ans, query(a[i]));
    cout << ans << endl;
    return 0;
}

注意这个main函数中的顺序，他是先insert完后才query的，所以绝对不可能会在查询的时候同层没有，因为你至少可以走你自己query这个数的路，我们是如果可以反向走就尽可能的反向走，但是一定是存在不反向走的路径的，

也就是说，如果我们把

        if (trie[p][!u]) 
        {
            p = trie[p][!u];
            res = (res << 1) + 1;
        }
        else if(trie[p][u])
        {
            p = trie[p][u];
            res = (res << 1) + 0;
        }

中的

        else if(trie[p][u])

删了，也是可以AC的

有道理 说的好

我觉得是因为既然有一步走到了这里，就一定有后面的节点，因为只要是一个数，插入的时候就不可能没有后面的低位节点。

大佬求解res=res*+1？

卜筮槅门 不是异或吗怎么成与或了

if(!son[p][u]) son[p][u]=++idx;
p = son[p][u];//指针指向下一层
各位佬，为什么这里改成p=idx；就是错误的呢

大佬 p=son[p][!u];和p=son[p][u];这两步是怎么判断的啊，没看懂

res 不能做全局变量
查询函数会改变res

思路牛逼，搞懂后来自菜鸡小白的赞叹