Trie 字典树

主要用途

• 给定$n$个字符串，多次询问，每次询问一个字符串是否出现过。
• 排序$n$个字符串。
• 将字符串映射到整数。
• 异或相关的问题。

可以注意到，结合C++中的

• string
• sort
• set
• map<string, int>

实际有用的部分很少。

询问最大异或

异或相关的问题
可以解决最大异或问题。

持久化

TRIE树和线段树类似，可以持久化。

参考题目

P8306 【模板】字典树

https://www.luogu.com.cn/problem/P8306

poj 3764

P4551 最长异或路径

https://www.luogu.com.cn/problem/P4551

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > a[100020];
int f[100020];
int t[4000020][2], tt;
int n, m, x, y, z;
void dfs(int x, int y) {
	for (int i = 0; i < a[x].size(); i++) {
		if (a[x][i].first != y) {
			f[a[x][i].first] = f[x] ^ a[x][i].second;
			dfs(a[x][i].first, x);
		}
	}
}
void insert(int x) {
	int p = 0;
	for (int i = 30; i >= 0; i--) {
		if (t[p][x >> i & 1] == 0) {
			t[p][x >> i & 1] = ++tt;
		}
		p = t[p][x >> i & 1];
	}
}
int query(int x) {
	int p = 0, re = 0;
	for (int i = 30; i >= 0; i--) {
		if (t[p][~x >> i & 1] > 0) {
			p = t[p][~x >> i & 1];
			re += 1 << i;
		} else {
			p = t[p][x >> i & 1];
		}
	}
	return re;
}
int main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> x >> y >> z;
		a[x].push_back(make_pair(y, z));
		a[y].push_back(make_pair(x, z));
	}
	dfs(1, 0);
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		insert(f[i]);
		ans = max(ans, query(f[i]));
	}
	cout << ans << endl;
	return 0;
}

P2922 [USACO08DEC]Secret Message G

https://www.luogu.com.cn/problem/P2922

#include <bits/stdc++.h>
using namespace std;
int t[500020][2];
int s[500020];
int c[500020];
int n, m, l, tt, x;
int a[10020];
int main()
{
	scanf("%d%d", &m, &n);
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &l);
		int p = 0;
		for (int j = 0; j < l; j++)
		{
			scanf("%d", &x);
			if (t[p][x] == 0)
			{
				t[p][x] = ++tt;
			}
			p = t[p][x];
			s[p]++;
		}
		c[p]++;
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &l);
		for (int j = 0; j < l; j++)
		{
			scanf("%d", &a[j]);
		}
		int p = 0, z = 0;
		bool flag = true;
		for (int j = 0; j < l; j++)
		{
			z += c[p];
			if (t[p][a[j]] == 0)
			{
				p = 0;
				break;
			}
			p = t[p][a[j]];
		}
		printf("%d\n", z + s[p]);
	}
	return 0;
}

P3065 [USACO12DEC]First! G

https://www.luogu.com.cn/problem/P3065

字符串可以排在第一个的条件

• 不存在一个更短的字符串是自己的前缀
• 在所有前缀相同的字符串中，自己的下一个字符必须是最小的
  • 可以得到一些字母之间的边，做拓扑排序，如果没有环就是可以的

#include <bits/stdc++.h>
using namespace std;
int n;
int t[300020][26], tt;
int v[300020];
void insert(const string &s)
{
	int p = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if (t[p][s[i] - 'a'] == 0)
		{
			t[p][s[i] - 'a'] = ++tt;
		}
		p = t[p][s[i] - 'a'];
	}
	v[p] = 1;
}
bool ok(const string &s)
{
	vector<int> a[26];
	int d[26] = {};
	int p = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if (v[p])
		{
			return false;
		}
		for (int j = 0; j < 26; j++)
		{
			if (t[p][j] && j != s[i] - 'a')
			{
				a[j].push_back(s[i] - 'a');
				d[s[i] - 'a']++;
			}
		}
		p = t[p][s[i] - 'a'];
	}
	queue<int> q;
	for (int i = 0; i < 26; i++)
	{
		if (d[i] == 0)
		{
			q.push(i);
		}
	}
	int c = 0;
	while (q.size())
	{
		c++;
		int u = q.front();
		q.pop();
		for (int i : a[u])
		{
			if (!--d[i])
			{
				q.push(i);
			}
		}
	}
	return c == 26;
}
int main()
{
	cin >> n;
	vector<string> s(n);
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
		insert(s[i]);
	}
	vector<string> z;
	for (int i = 0; i < n; i++)
	{
		if (ok(s[i]))
		{
			z.push_back(s[i]);
		}
	}
	cout << z.size() << endl;
	for (string i : z)
	{
		cout << i << endl;
	}
	return 0;
}

阅读其他

AC自动机