19.Trie

• Trie字符串统计

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int son[N][26],cnt[N],idx;
char str[N];
void Insert(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
int Query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char a[2];
        scanf("%s%s",a,str);
        if(a[0]=='I') Insert(str);
        else  cout<<Query(str)<<endl;
    }
    return 0;
}

• 最大异或对

思路：

一个整数,是可以转化成为一个32位的二进制数,而也就可以变成长度为32位的二进制字符串.
既然如此话,那么我们可以这么做,每一次检索的时候,我们都走与当前a[i]这一位相反的（比如当前这一位是0，我们就看一看下一个节点的1有没有，有的话要往1走）,也就是让or值最大,如果说没有路可以走的话,那么就走相同的了.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=3e6+10;
int son[M][2],idx;
int a[N];
void Insert(int x)
{
    int p=0;
    for(int i=30;~i;i--)
    {
        int temp=x>>i&1;//返回x的2进制展开里的第i位是0还是1
        if(!son[p][temp])
            son[p][temp]=++idx;
        p=son[p][temp];
    }
}
int Query(int x)
{
    int p=0,res=0;
    for(int i=30;~i;i--)
    {
        int temp=x>>i&1;
        if(son[p][!temp])
        {
            res+=1<<i;//可以贡献一个i位的(1000...)
            p=son[p][!temp];
        }
        else p=son[p][temp];
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        Insert(a[i]);
    }
    int res=0;
    for(int i=0;i<n;i++)
    {
        res=max(res,Query(a[i]));
    }
    cout<<res<<endl;
    return 0;
}