知識概覽

• Trie：高效地存儲和查找字符串集合的數據結構
• 數字、漢字可以用二進制位來存

例題展示

題目鏈接

Trie字符串統計：

https://www.acwing.com/problem/content/837/

代碼

#include <cstdio>const int N = 100010;int son[N][26], cnt[N], idx;  // 下標是0的點，既是根節點，又是空節點
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;scanf("%d", &n);while (n--){char op[2];scanf("%s%s", op, str);if (op[0] == 'I') insert(str);else printf("%d\n", query(str));}return 0;
}

題目鏈接

最大異或對：

https://www.acwing.com/problem/content/145/

題解

對于每個數，先插入，然后再找和這個數異或最大的數，找的方法是找已存儲在字典樹的數，從高位到低位，盡量找和當前數該位不同的數。最終得到的數即為所求。

代碼

#include <cstdio>
#include <algorithm>using namespace std;const int N = 100010, M = 31 * N;int n;
int son[M][2], idx, x;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 p = 0, res = 0;for (int i = 30; i >= 0; i--){int u = x >> i & 1;if (son[p][!u]){p = son[p][!u];res = res * 2 + !u;}else{p = son[p][u];res = res * 2 + u;}}return res;
}int main()
{scanf("%d", &n);int res = 0;for (int i = 0; i < n; i++){scanf("%d", &x);insert(x);int t = query(x);res = max(res, x ^ t);}printf("%d\n", res);return 0;
}