字符串统计

法一：Trie树

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int son[N][26];
int cnt[N];
int idx;
int n;
void insert(string s)
{
    int p=0;
    for (int i=0;i<s.size();i++)
    {
        int u = s[i]-'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p=son[p][u];
    }
    cnt[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;
        p=son[p][u];
    }
    return cnt[p];
}
int main()
{
    scanf("%d",&n);
    while (n--)
    {
        string ch,s;
        cin>>ch>>s;
        if (ch[0]=='I') insert(s);
        else printf("%d\n",query(s));
    }
    return 0;
}

法二：哈希表干就完了

#include <bits/stdc++.h>
using namespace std;
unordered_map<string,int>S;
int n;
int main()
{
    cin>>n;
    while (n--)
    {
        string ch,s;
        cin>>ch>>s;
        if (ch[0]=='I') S[s]++;
        else cout<<S[s]<<endl;
    }
    return 0;
}

最大异或对

字典树应用的绝对好题，收获满满~

最直观的想法，暴力就完事儿了（肯定TLE，$O(n^2)$）

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%d",&a[i]);
    int ans = 0;
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<i;j++)
            ans = max(ans,a[i]^a[j]);
    }
    printf("%d\n",ans);
    return 0;
}

字典树上了，思路清晰，代码逻辑也很清晰

我们分析发现，要想优化两重循环的暴力，第一层没法再优化了，必须要枚举一遍
那就是优化内层遍历的情况,也就是快速得到与当前枚举的数异或最大的数字是哪个数

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 31*N; //每一个数最多31位  
int a[N]; 
int idx;
int son[M][2]; //每一节点最多有2个叉
int n;
    void insert(int x) //和字符串的字典树一模一样~
{
    int p = 0;
    for (int i=30;i>=0;i--)
    {
        int u = x>>i&1;
        if (!son[p][u]) son[p][u] = ++idx;
        p=son[p][u];
    }
}
int query(int x)
{
    int res=0; //得到与x异或最大的数是哪一个数
    int p = 0;
    for (int i=30;i>=0;i--)
    {
        int u =x>>i&1;
        if (son[p][!u]) //我们知道，每次走的分叉最好是与当前位置不同的数字所在的路径
        {
            p=son[p][!u];
            res = (res<<1)+!u; // 相当于 res = res*2+!u
        }
        else //如果当前分叉只有一个叉，且此叉的数字又和要异或的数的当前位置数字相同，那也没办法，只能走下去
        {
            p=son[p][u];
            res=(res<<1)+u; //相当于 res = res*2+u
        }
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%d",&a[i]);

    int ans = 0;
    for (int i=0;i<n;i++) 
    {
        insert(a[i]); //先存进来这个数，避免一开始的空节点的单独判断
        int t = query(a[i]); //得到了目前与a[i]异或最大的数
        ans = max(ans,a[i]^t); //随即更新一下答案
    }
    printf("%d\n",ans);
    return 0;
}

前缀统计

模板题的应用

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010,M = 2*100010;
int son[N][26];
int cnt[M];
int n,m;
int idx;
void insert(string s)
{
    int p =0;
    for (int i=0;i<s.size();i++)
    {
        int u = s[i]-'a';
        if (!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
int query(string s)
{
    int p = 0;
    int ans = 0;
    for (int i=0;i<s.size();i++)
    {
        int u = s[i]-'a';
        p=son[p][u];  //先去看一下当前字母的下一个位置情况
        if (p==0) return ans; //如果下一个位置为0，此时说明没有符合的情况了，返回答案
        ans+=cnt[p]; //答案更新
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    while (n--)
    {
        string s;
        cin>>s;
        insert(s);
    }
    while (m--)
    {
        string s;
        cin>>s;
        cout<<query(s)<<endl;
    }
    return 0;
}