835. Trie字符串统计，836。最大异或对，(Tire树，字典树)

835. Trie字符串统计

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

维护一个字符串集合，支持两种操作：

1. I x 向集合中插入一个字符串 x

1. ；
2. Q x 询问一个字符串在集合中出现了多少次。

共有 N

个操作，输入的字符串总长度不超过 105

，字符串仅包含小写英文字母。

输入格式

第一行包含整数 N

，表示操作数。

接下来 N

行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x

在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗104

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

 

 * 由于字符串长度最多出现 1e5 个字符，所以一棵树最多有 1e5 层，又由于只有26个小写
 * 字母，那么每一个节点都需要预留 26 个子节点，因此开一个二维数组即可；
 *
 * 我们能保证每一个不同的前缀都处于不同的层；
 *
 * 但是我们又如何知道一个单词是否出现过，我们可以为每一个单词的尾字母所得到的儿子
 * 节点的值（它所处于的那一层的编号）（不同的单词的儿子节点的值一定是不相同的），
 * 作为 cnt 数组的下标，然后cnt[p]++ 表示以 这个单词结尾的个数得加一，同时又表示
 * 出了这是一个单词，而不是一个单词的前缀，处于前缀的单词此时还在for循环中探索字符
 * 的奥秘；(cnt 初始值等于0);

/**
 * 由于字符串长度最多出现 1e5 个字符，所以一棵树最多有 1e5 层，又由于只有26个小写
 * 字母，那么每一个节点都需要预留 26 个子节点，因此开一个二维数组即可；
 * 
 * 我们能保证每一个不同的前缀都处于不同的层；
 * 
 * 但是我们又如何知道一个单词是否出现过，我们可以为每一个单词的尾字母所得到的儿子
 * 节点的值（它所处于的那一层的编号）（不同的单词的儿子节点的值一定是不相同的），
 * 作为 cnt 数组的下标，然后cnt[p]++ 表示以 这个单词结尾的个数得加一，同时又表示
 * 出了这是一个单词，而不是一个单词的前缀，处于前缀的单词此时还在for循环中探索字符
 * 的奥秘；(cnt 初始值等于0);
*/
 
 
#include <iostream>
#include <string>
 
using namespace std;
 
const int maxn = 1e5+10;
int son[maxn][26],idx;
int cnt[maxn];
 
void insert(string s)
{
    int p=0;    //单词的首字母存在第0行
    for(int i=0;i<s.size();++i)
    {
        int u=s[i]-'a';
        if(!son[p][u])  //如果这个单词没出现过，
            son[p][u]=++idx; //就将这个单词的这个字母存在son 数组的p行u列；
        p=son[p][u];    //继续探寻这个单词的下一个字母
    }
    ++cnt[p];   //p或者是之前出现过，或者是idx的值；但不管是哪一种情况，
}               //都能保证每个不同的单词最后得到的p值一定是独一无二的；
 
int query(string s)
{
    int p=0;
    for(int i=0;i<s.size();++i)
    {
        int u=s[i]-'a';
        if(!son[p][u])  //如果这个字母从来没出现过，那么这个单词必定没出现过，
            return 0;   //直接返回0；
        p=son[p][u];
    }
    return cnt[p];  //如果这个单词出现过，那么返回这个单词出现的次数；
}                   //也有可能这个单词没出现过，但是是某个单词的前缀，也返回0；
 
int main()
{
    int n;
    cin >> n;
    
    for(int i=0;i<n;++i)
    {
        string op,s;
        cin >> op >> s;
        if(op == "I")
            insert(s);
        else
            cout << query(s) << endl;
            
    }
    return 0;
}

 

143. 最大异或对

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

在给定的 N

个整数 A1，A2……AN 中选出两个进行 xor

（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 N

。

第二行输入 N

个整数 A1～AN

。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤105

,
0≤Ai<231

输入样例：

3
1 2 3

输出样例：

3

 

 * 在n个数中选择两个数异或，当两个数的高位第一次不同时，此时的高位越高，那么这两个数
 * 的异或值就越大；
 *
 * 那么我们在选择 与x 的异或值最大的时候，我们必定选择其他数的二进制数的高位（第t位）
 * 与x的二进制数相同的高位（第t位）的二进制值（0，1）不同的数（y）；
 * 那么我们把每一个数的二进制位存到字典树中，再查询与x异或值最大的值（这值就在这n个
 * 数的当中）是多少；
 * 把所有的数的异或值最大的数算出来，再进行比较，最后得到的最大的数就是答案；

/**
 * 在n个数中选择两个数异或，当两个数的高位第一次不同时，此时的高位越高，那么这两个数
 * 的异或值就越大；
 * 
 * 那么我们在选择 与x 的异或值最大的时候，我们必定选择其他数的二进制数的高位（第t位）
 * 与x的二进制数相同的高位（第t位）的二进制值（0，1）不同的数（y）；
 * 那么我们把每一个数的二进制位存到字典树中，再查询与x异或值最大的值（这值就在这n个
 * 数的当中）是多少；
 * 把所有的数的异或值最大的数算出来，再进行比较，最后得到的最大的数就是答案；
*/
 
 
#include <iostream>
 
using namespace std;
 
const int maxn = 1e5+10;
int a[maxn];
int son[maxn*31][2],idx;
 
void insert(int v)
{
    int p=0;
    for(int i=30;i>=0;--i)
    {
        int u=(v>>i) & 1;
        if(!son[p][u])
            son[p][u]=++idx;
        p=son[p][u];
    }   //此题为什么没有cnt数组，因为每个数的二进制位数都是一样的，都是32位，
}       //最高位是符号位，就不进行运算了；
 
int query(int x)
{
    int p=0,res=0;
    for(int i=30;i>=0;--i)
    {
        int u=(x>>i)  & 1;  //求x的第i位的二进制数是多少；
        if(son[p][!u])  //如果u的兄弟节点存在（子节点最多存在两位）
        {
            p=son[p][!u];
            res=2*res+!u;   
        }
        else
        {
            p=son[p][u];
            res=2*res+u;
        }
    }
    
    return res;
}
 
int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;++i)
    {
        cin >> a[i];
        insert(a[i]);
    }
    
    int res =0;
    
    for(int i=0;i<n;++i)
    {
        int v=query(a[i]);
        res = max(res,a[i]^v);
    }
    
    cout << res << endl;
    
    return 0;
    
}