7 条题解

  • 4
    @ 2022-9-6 14:48:36

    楼上使用的是递归版的01Trie插入。 我用的循环的方式:

    #include <bits/stdc++.h>
    #include <cstdlib>
    
    using namespace std;
    
    const int N=31000010;
    int son[N][2];
    int cnt[N];
    int idx;
    
    int read()
    {
        int x=0,f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9')
        {
        	ch=getchar();
        	if(ch=='-')f=-1;
        }
        while('0'<=ch&&ch<='9')
        {
        	x=x*10+ch-'0';
        	ch=getchar();
        }
        return x*f;
    }
    
    void insert(int x)
    {
        int p=0;
        for(int i=31;i>=0;i--)
        {
            int u=x>>i&1;
            if(!son[p][u])son[p][u]=++idx;
            p=son[p][u];
        }
        cnt[p]++;
    }
    
    int n;
    int res=0x80808080;
    
    int findxor(int x)
    {
        int p=0,res=0;
        for(int i=31;i>=0;i--)
        {
            int u=x>>i&1;
            if(son[p][!u])p=son[p][!u],res+=1<<i;
            else p=son[p][u];
        }
        return res;
    }
    
    int a[N];
    
    int main()
    {
        n=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            insert(a[i]);
        }
        for(int i=1;i<=n;i++)res=max(res,findxor(a[i]));
        printf("%d\n",res);
        return 0;
    }
    

信息

ID
94
时间
1000ms
内存
256MiB
难度
4
标签
递交数
682
已通过
165
上传者