字典树用于快速查询字符串
字典树的几种操作:

  • 把字符串插入字典树
void insert(string s)
{
     int p=0;
     for(int i=0;i<s.size();i++)
     {
         int q=s[i]-'a';
         if(!a[p][q]) a[p][q]=index++;	//不存在则创建
         p=a[p][q];
     }
     num[p]++;	//出现的次数+1
}
  • 查询字符串是否在字典树中,查询字符串在字典树中出现的次数
int query(string s)
{
     int p=0;
     for(int i=0;i<s.size();i++)
     {
         int q=s[i]-'a';
         if(!a[p][q]) return 0;		
         p=a[p][q];
     }
     return num[p];

例题

维护一个字符串集合,支持两种操作:

  1. I x 向集合中插入一个字符串 xx;
  2. Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作,输入的字符串总长度不超过 105,字符串仅包含小写英文字母。

输入格式

第一行包含整数 N,表示操作数。

接下来 N 行,每行包含一个操作指令,指令为 I xQ x 中的一种。

输出格式

对于每个询问指令 Q x,都要输出一个整数作为结果,表示 x 在集合中出现的次数。

每个结果占一行。

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

const int N=1e6;
int a[N][26],num[N];	
int index=1;	//字典树元素下标

//创建字典树,把字符串插入进去
void insert(string s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int u=s[i]-'a';		//把char转为int
        if(!a[p][u]) a[p][u]=index++;	//不存在则创建
        p=a[p][u];		
    }
    num[p]++;	//以p结尾的字符串个数+1
}

//查询该字符串出现的次数
int query(string s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int u=s[i]-'a';
        if(!a[p][u]) return 0;
        p=a[p][u];
    }
    return num[p];			//返回字符串出现的次数
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char c;
        cin>>c;
        if(c=='I')
        {
            string s;
            cin>>s;
            insert(s);
        }
        else
        {
            string s;
            cin>>s;
            cout<<query(s)<<endl;
        }
    }
    
}

最大异或对

在给定的 N 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?

输入格式

第一行输入一个整数 N。

第二行输入 N 个整数 A1~AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤1051≤N≤105,
0≤Ai<231

思路:要想使异或值最大,则需要从最高位开始的值尽量为1;
则,对于n,若n的最高位为1,则需要找到最高位为0的数,异或值为1,相反同理。
对每个元素构建字典树,找到对应的最大值即可。

#include<iostream>
using namespace std;

const int N=1e7;
int arr[N];
int tr[N][2];
int ans=0,index=1;

void insert(int x)
{
    int p=0;
    for(int i=31;i>=0;i--)
    {
        int t=x>>i&1;		//从高位开始取得二进制数
        if(!tr[p][t])  tr[p][t]=index++;
        p=tr[p][t];
    }
}

int query(int x)
{
    int p=0;
    int ans=0;
    for(int i=31;i>=0;i--)
    {
        int t=x>>i&1;
        if(tr[p][!t]) 
        {
            ans=ans*2+!t;
            p=tr[p][!t];
        }
        else
        {
            ans=ans*2+t;
            p=tr[p][t];
        }
    }
    return ans;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    
    for(int i=0;i<n;i++)
    {
        insert(arr[i]);
        int t=query(arr[i]);
        ans=max(ans,t^arr[i]);
    }
    cout<<ans;
}

Q.E.D.