字典树 trie

就是一棵树（完结

又回来了......

一棵树，每个节点可以表示一个字母

like this

Ps: p_2是因为画图工具的原因，实际上是p

那么，看这颗树。构成这颗树的单词可能不唯一。看下面例子。

现在来了一个单次 apple。我们发现 root（空）的下面没有 a ， 新建一个a，现在发现a的下面没有p, 添加 p，以此类推。

第二个单词 apz 来了，发现 a有了, 发现 a 的后面有 p， 但后面没有 z， 新建。

又有单词 bo，按照上面方法新建。

看似一切没有问题。

但是问题来了，如果加一个 appl,ap, b呢？树不会发生改变，此时，我们需要一个cnt。

#include <cstring>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

const int kMaxN = 3e6 + 5;

int n, t, a[kMaxN][90], cnt, ans, Cnt[kMaxN], q;
string s;

int zhuan(char x) { //将字母转换编号
  if (x >= 'A' && x <= 'Z') {
    return x - 'A';
  } else if (x >= 'a' && x <= 'z') {
    return x - 'a' + 26;
  } else {
    return x - '0' + 52;
  }
}

void Add(string s) { //添加单词
  int p = 0, l = s.size();
  for (int i = 0; i < l; i++) {
    int c = zhuan(s[i]);
    if (!a[p][c]) { //没出现
      a[p][c] = ++cnt; 
    }
    p = a[p][c]; //转移
  }
  Cnt[p]++; //标记

}

int check(string s) {
  int p = 0, ok = 0, l = s.size();
  for (int i = 0; i < l; i++) {
    int c = zhuan(s[i]);
    if (!a[p][c]) { //同理，查询失败
      return 0;
    }
    p = a[p][c];
  }
  return Cnt[p]; //返回次数
}

int main() 
   cin >> n >> t;
   for (int i = 1; i <= cnt; i++) {
     Cnt[i] = 0;
   }
   cnt = 0;
   for (int i = 1; i <= n; i++) {
     cin >> s;
     Add(s);
   }
   for (int i = 1; i <= t; i++) {
     ans = 0;
     cin >> s;
     cout << check(s) << '\n';
   }
  return 0;
}

这里不是模板题，而是实现了一个近似于hash的功能，判断出现了几个这个单词

接下开开始一个 01字典树

顾名思义， 01字典树就是将原本的字母变成01，其构建思路是一样的。

因为 它/他/她 只有 01，那么用途也有所改变。

最常见的用的就是最大异或值，利用贪心的思想， ^相同为0， 不同为1.最大就尽量不同。

CF706D

#include <iostream>

using namespace std;

const long long kMaxN = 6e6;

long long n, tree[kMaxN][2], Cnt[kMaxN], tot;
char c;

void update(long long x, long long op) {
  long long p = 0;
  for (long long i = 30; i >= 0; i--) {
    long long t = x >> i & 1;
    if (!tree[p][t]) {
      tree[p][t] = ++tot;
    }
    p = tree[p][t];
    Cnt[p] += op;
  }
}

long long Ans(long long x) {
  long long p = 0, ans = 0;
  for (long long i = 30; i >= 0; i--) {
    long long t = (x >> i & 1) ^ 1; //不一样的
    if (tree[p][t] && Cnt[tree[p][t]]) {  //能不一样
      p = tree[p][t];
      ans = ans << 1 | 1;
    } else {
      p = tree[p][t ^ 1]; //没得
      ans = ans << 1;
    }
  }
  return ans;
}

int main() {
  cin >> n;
  update(0, 1);
  for (long long i = 1, x; i <= n; i++) {
    cin >> c >> x;
    if (c == '?') {
      cout << Ans(x) << '\n';
    } else {
      update(x, (c == '+' ? 1 : -1));
    }
  }
  return 0;
}