东莞网络网站建设,群晖 wordpress 迁移,拓者室内设计吧官网,网页设计教程步骤Trie树又称字典树#xff0c;前缀树。是一种可以高效查询前缀字符串的树#xff0c;典型应用是用于统计#xff0c;排序和保存大量的字符串#xff08;但不仅限于字符串#xff09;#xff0c;所以经常被搜索引擎系统用于文本词频统计。 它的优点是#xff1a;利用字符串… Trie树又称字典树前缀树。是一种可以高效查询前缀字符串的树典型应用是用于统计排序和保存大量的字符串但不仅限于字符串所以经常被搜索引擎系统用于文本词频统计。 它的优点是利用字符串的公共前缀来减少查询时间最大限度地减少无谓的字符串比较查询效率比哈希树高。做题看到大量字符串或者大量字符就往Trie树或者哈希这边想因为速度很快. AcWing 835. Trie字符串统计
https://www.acwing.com/activity/content/problem/content/883/
维护一个字符串集合支持两种操作
I x 向集合中插入一个字符串 x x xQ x 询问一个字符串在集合中出现了多少次。
共有 N N N 个操作所有输入的字符串总长度不超过 1 0 5 10^5 105字符串仅包含小写英文字母。
输入格式
第一行包含整数 N N N表示操作数。
接下来 N N N 行每行包含一个操作指令指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x都要输出一个整数作为结果表示 x x x 在集合中出现的次数。
每个结果占一行。
数据范围 1 ≤ N ≤ 2 ∗ 1 0 4 1 \le N \le 2*10^4 1≤N≤2∗104
输入样例
5
I abc
Q abc
Q ab
I ab
Q ab输出样例
1
0
1思路
Trie树模版题
代码
/*** https://www.acwing.com/problem/content/837/*/
#include bits/stdc.h#define int long long
using namespace std;const int N 1e5 10;
int son[N][26], cnt[N], idx;
// 下标0代表根节点和空节点cnt用于计数idx代表结点的索引void insert(string s) {int x 0;for (auto c: s) {int y c - a;if (!son[x][y]) son[x][y] idx;// 没有该子结点就创建一个x son[x][y]; // 走到该子节点}cnt[x];// 标记该子节点存在的单词个数
}int query(string s) {int x 0;for (auto c: s) {int y c - a;if (!son[x][y]) return 0;// 没有该子结点就返回查询不到x son[x][y];}return cnt[x];
}signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifint n;cin n;while (n--) {string op, s;cin op s;if (op I) insert(s);else cout query(s) endl;}return 0;
}【模板】字典树
https://www.luogu.com.cn/problem/P8306
题目描述
给定 n n n 个模式串 s 1 , s 2 , … , s n s_1, s_2, \dots, s_n s1,s2,…,sn 和 q q q 次询问每次询问给定一个文本串 t i t_i ti请回答 s 1 ∼ s n s_1 \sim s_n s1∼sn 中有多少个字符串 s j s_j sj 满足 t i t_i ti 是 s j s_j sj 的前缀。
一个字符串 t t t 是 s s s 的前缀当且仅当从 s s s 的末尾删去若干个可以为 0 个连续的字符后与 t t t 相同。
输入的字符串大小敏感。例如字符串 Fusu 和字符串 fusu 不同。
输入格式
本题单测试点内有多组测试数据。
输入的第一行是一个整数表示数据组数 T T T。
对于每组数据格式如下 第一行是两个整数分别表示模式串的个数 n n n 和询问的个数 q q q。 接下来 n n n 行每行一个字符串表示一个模式串。 接下来 q q q 行每行一个字符串表示一次询问。
输出格式
按照输入的顺序依次输出各测试数据的答案。 对于每次询问输出一行一个整数表示答案。
样例 #1
样例输入 #1
3
3 3
fusufusu
fusu
anguei
fusu
anguei
kkksc
5 2
fusu
Fusu
AFakeFusu
afakefusu
fusuisnotfake
Fusu
fusu
1 1
998244353
9样例输出 #1
2
1
0
1
2
1提示
数据规模与约定
对于全部的测试点保证 1 ≤ T , n , q ≤ 1 0 5 1 \leq T, n, q\leq 10^5 1≤T,n,q≤105且输入字符串的总长度不超过 3 × 1 0 6 3 \times 10^6 3×106。输入的字符串只含大小写字母和数字且不含空串。
说明
std 的 IO 使用的是关闭同步后的 cin/cout本题不卡常。
思路
因为这里需要统计的是前缀因此每走一个点都需要将cnt数组加1
这里不仅有小写还有大写和数字可以把小写映射为0-26,大写映射为26-52,数字映射为36-62 ,都是左闭右开区间。
有多组测试数据需要初始化son为0idx为0cnt为0
数据比较大需要开cin和cout优化 Trie第一维开多大取决于字符串长度,与idx能增长到多少有关尽可能开大一点5e6没问题第二维取决于字符串里面字符的个数 代码
/*** https://www.luogu.com.cn/problem/P8306*/
#include bits/stdc.h#define int long long
using namespace std;//空间怎么看开多大看数据范围 输入总字符串总长度不超过3e6
const int N 3e6 10;
int son[N][65], cnt[N], idx;int get(char c) {if (c a c z) return c - a;if (c A c Z) return c - A 26;if (c 0 c 9) return c - 0 26 26;}void insert(string s) {int x 0;for (char c: s) {int y get(c);if (!son[x][y]) son[x][y] idx;x son[x][y];cnt[x];}
}int query(string s) {int x 0;for (auto c: s) {int y get(c);if (!son[x][y]) return 0;x son[x][y];}return cnt[x];
}void solve() {int n, q;cin n q;string s;while (n--) { cin s, insert(s); }while (q--) { cin s, cout query(s) \n; }//清空字典树,不使用memset,使用forfor (int i 0; i idx; i) {for (int j 0; j 63; j) {son[i][j] 0;}}for (int i 0; i idx; i) cnt[i] 0;idx 0;
}signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifcin.tie(0), cout.tie(0), ios::sync_with_stdio(false);int t;cin t;while (t--) solve();return 0;
}AcWing 143. 最大异或对
在给定的 N N N 个整数 A 1 A 2 … … A N A_1A_2……A_N A1A2……AN 中选出两个进行 x o r xor xor异或运算得到的结果最大是多少
输入格式
第一行输入一个整数 N N N。
第二行输入 N N N 个整数 A 1 A_1 A1 A N A_N AN。
输出格式
输出一个整数表示答案。
数据范围 1 ≤ N ≤ 1 0 5 1 \le N \le 10^5 1≤N≤105, 0 ≤ A i 2 31 0 \le A_i 2^{31} 0≤Ai231
输入样例
3
1 2 3输出样例
3思路
先将所有数插入到01Trie树中然后遍历一遍数组去找可以使得和他异或起来最大的数时间复杂度是 n l o g n nlogn nlogn的因为树每层最多30个.
如何找异或起来最大
比如当前节点为0那就看!0的节点是否存在如果存在走过去一定是最优的因为在这一位异或起来的结果就可以变成1了否则只能往0走。
代码
/*** https://www.acwing.com/problem/content/145/*/
#include bits/stdc.h#define int long long
using namespace std;const int N 1e5 10;
int son[N * 32][2], idx;void insert(int t) {int x 0;for (int i 30; i 0; i--) {int y t i 1;if (!son[x][y]) son[x][y] idx;x son[x][y];}
}int query(int t) {int x 0, res 0;for (int i 30; i 0; i--) {int y t i 1;if (son[x][!y]) {//另一个存在res res * 2 !y;x son[x][!y];} else {res res * 2 y;x son[x][y];}}return res;
}signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifint n;cin n;vectorint a(n);for (int i 0; i n; i)cin a[i];for (int i 0; i n; i) insert(a[i]);int mx 0;for (int i 0; i n; i) mx max(mx, a[i] ^ query(a[i]));cout mx endl;return 0;
}最长异或路径
题目描述
给定一棵 n n n 个点的带权树结点下标从 1 1 1 开始到 n n n。寻找树中找两个结点求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入格式
第一行一个整数 n n n表示点数。
接下来 n − 1 n-1 n−1 行给出 u , v , w u,v,w u,v,w 分别表示树上的 u u u 点和 v v v 点有连边边的权值是 w w w。
输出格式
一行一个整数表示答案。
样例 #1
样例输入 #1
4
1 2 3
2 3 4
2 4 6样例输出 #1
7提示
最长异或序列是 1 , 2 , 3 1,2,3 1,2,3答案是 7 3 ⊕ 4 73\oplus 4 73⊕4。
数据范围 1 ≤ n ≤ 100000 ; 0 u , v ≤ n ; 0 ≤ w 2 31 1\le n \le 100000;0 u,v \le n;0 \le w 2^{31} 1≤n≤100000;0u,v≤n;0≤w231。
思路
要求两个点之间的所有元素的异或值设为 i , j i,j i,j两点 可以变成 i i i到根节点异或 j j j到根节点的异或值。 因此我们可以去求每个点到根节点1的异或值使用dfs即可记录在sum中
然后遍历每个点求当前点到根节点亦或值sum[i]可以异或得到的最大值。
之后就和上面一题一样了
代码
#include bits/stdc.husing namespace std;typedef struct edge {int to, w;
} edge;const int N 1e5 10;
int son[N * 31][2], cnt[N], idx;
int sum[N];// 存到根节点到异或值
vectoredge e[N];
int n;void dfs(int x, int fa) {for (auto [y, w]: e[x]) {if (y fa) continue;sum[y] sum[x] ^ w;dfs(y, x);}
}void insert(int t) {int x 0;for (int i 30; i 0; i--) {int y t i 1;if (!son[x][y]) son[x][y] idx;x son[x][y];}
}int query(int t) {int x 0, res 0;for (int i 30; i 0; i--) {int y t i 1;if (son[x][!y]) {res 1 i;x son[x][!y];} else {x son[x][y];}}return res;
}signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifcin n;for (int i 1; i n - 1; i) {int x, y, w;cin x y w;e[x].push_back({y, w});e[y].push_back({x, w});}dfs(1, 0);for (int i 1; i n; i) insert(sum[i]);int res 0;for (int i 1; i n; i) res max(res, query(sum[i]));cout res endl;return 0;
}最小异或对
题目描述
https://ac.nowcoder.com/acm/contest/53485/F
给出一个多重集合(元素可以重复的集合),你需要提供以下操作:
ADD x,向多重集合里添加一个元素x,多重集合内元素可以重复**DEL x,**从多重集合中删除一个元素x,保证要删除的元素一定存在,如果存在多个x则仅删除其中任意1个QUE,查询集合中的最小异或对的值,即找到集合中任何**两个元素(可以相等)**异或能得到的最小值,保证询问时集合包含的元素数量不少于2个
对于每个QUE操作,你需要输出查询的结果.
以上操作中涉及的操作数x均为非负整数. 1 n 2 ∗ 1 0 5 , 0 x 2 30 1n2*10^5 ,0x2^{30} 1n2∗105,0x230
思路-01Trie
与最大异或对类似
思路-结论
最小异或对的结论最小异或对一定为数组排序后相邻两个数的异或值 证明 设 a b c abc abc,我们现在需要证明最小异或对只可能是ab或者bc 设c与a的第一个不同的位为第x位(从高向低看),则x位上面c一定为1a一定为0 ,b可以为0或者1 a,b,c在x位置之前的数字都是相同的。 因此在x位上面ac的这一位一定为1ab和b^c一定会有一个异或起来在这一位为0 因此a^c不可能是最小的也就是一定是相邻两个数异或起来才是最小。 可以使用平衡树进行增删改查操作.
代码
#include bits/stdc.h#define int long long
using namespace std;multisetint s, res;
int n, x;
string op;void add() {auto it s.lower_bound(x);if (it ! s.end()) res.insert(x ^ *it);if (it ! s.begin()) res.insert(x ^ *prev(it));if (it ! s.end() it ! s.begin()) res.erase(res.lower_bound(*it ^ *prev(it)));s.insert(x);
}void del() {s.erase(s.find(x));auto it s.lower_bound(x);if (it ! s.end()) res.erase(res.find(x ^ *it));if (it ! s.begin()) res.erase(res.find(x ^ *prev(it)));if (it ! s.end() it ! s.begin()) res.insert(*it ^ *prev(it));
}int que() {return *res.begin();
}signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifcin n;while (n--) {cin op;if (op ADD) {cin x;add();} else if (op DEL) {cin x;del();} else cout que() endl;}return 0;
}
