5 条题解

  • 0
    @ 2023-10-11 20:03:41
    #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;
    }
    

    基础的 $\tt 01Trie

    信息

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