百度站长平台清退常熟做网站推广的

百度站长平台清退,常熟做网站推广的,产业园网站建设方案,网站建设 好的公司1. 字典树的概念 Trie 树⼜叫字典树或前缀树#xff0c;是⼀种能够快速插⼊和查询字符串的数据结构。它利⽤字符串的公共前 缀#xff0c;将字符串组织成⼀棵树形结构#xff0c;从⽽⼤ 提⾼了存储以及查找效率。 我们可以把字典树想象成⼀棵多叉树#xff0c;每⼀条边代表…1.字典树的概念Trie 树⼜叫字典树或前缀树是⼀种能够快速插⼊和查询字符串的数据结构。它利⽤字符串的公共前 缀将字符串组织成⼀棵树形结构从⽽⼤ 提⾼了存储以及查找效率。我们可以把字典树想象成⼀棵多叉树每⼀条边代表⼀个字符从根节点到某个节点的路径就代表了⼀个字符串。例如要存储abc、abd、acde以及cd时构建的字典树如下2.字典树的作⽤当我们在字典树的每⼀个结点位置额外维护⼀些信息时就可以做到很多事情• 查询某个单词是否出现过并且出现⼏次• 查询有多少个单词是以某个字符串为前缀• 查询所有以某个前缀开头的单词这个作⽤可以⽤到输⼊法中输⼊拼⾳的时候可以提⽰可能 的单词当然除了上述作⽤以外字典树还可以解决别的问题后续可以在做题中体会。3.字典树的实现实现⼀个能够查询单词出现次数以及查询有多少个单词是以某个字符串为前缀的字典树默认全是⼩ 写字⺟。准备⼯作#include iostream #include cstring using namespace std; const int N 1e6 10; int tree[N][26], p[N], e[N]; int idx;插⼊字符串void insert(string s) { int cur 0; // 从根结点开始 p[cur]; // 这个格⼦经过⼀次 for(auto ch : s) { int path ch - a; // 如果没有路 if(tree[cur][path] 0) tree[cur][path] idx; cur tree[cur][path]; p[cur]; } e[cur]; }查询字符串出现的次数int find(string s) { int cur 0; for(auto ch : s) { int path ch - a; if(tree[cur][path] 0) return 0; cur tree[cur][path]; } return e[cur]; }查询有多少个单词以字符串s为前缀int find_pre(string s) { int cur 0; for(auto ch : s) { int path get_num(ch); if(tree[cur][path] 0) return 0; cur tree[cur][path]; } return p[cur]; }4.1【模板】字典树题⽬来源 洛⾕题⽬链接P8306 【模板】字典树难度系数 ★★题目描述给定 n 个模式串 s1​,s2​,…,sn​ 和 q 次询问每次询问给定一个文本串 ti​请回答 s1​∼sn​ 中有多少个字符串 sj​ 满足 ti​ 是 sj​ 的前缀。一个字符串 t 是 s 的前缀当且仅当从 s 的末尾删去若干个可以为 0 个连续的字符后与 t 相同。输入的字符串大小敏感。例如字符串Fusu和字符串fusu不同。输入格式本题单测试点内有多组测试数据。输入的第一行是一个整数表示数据组数 T。对于每组数据格式如下第一行是两个整数分别表示模式串的个数 n 和询问的个数 q。接下来 n 行每行一个字符串表示一个模式串。接下来 q 行每行一个字符串表示一次询问。输出格式按照输入的顺序依次输出各测试数据的答案。对于每次询问输出一行一个整数表示答案。输入输出样例输入 #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≤105且输入字符串的总长度不超过 3×106。输入的字符串只含大小写字母和数字且不含空串。说明std 的 IO 使用的是关闭同步后的 cin/cout本题不卡常。【解法】模板题仅需维护⼀个 p 数组查询多少前缀即可。【参考代码】#include iostream #include string #include cstring using namespace std; const int N 3e6 10; // 字典树节点最大数量根据数据范围设定 int tr[N][62]; // 字典树tr[节点][字符编号] 子节点编号 int p[N]; // p[节点]以该节点为前缀的模式串数量 int idx; // 字典树节点计数器初始为0根节点是0 // 将字符映射为0-61的编号区分大小写字母数字 int get_num(char ch) { if (ch a ch z) { return ch - a; // 小写字母0-25 } else if (ch A ch Z) { return ch - A 26; // 大写字母26-51 } else { return ch - 0 52; // 数字52-61 } } // 插入模式串到字典树中 void insert(string s) { int cur 0; // 从根节点开始 p[cur]; // 根节点是所有字符串的前缀计数1 for (char ch : s) { int path get_num(ch); // 获取当前字符的编号 if (tr[cur][path] 0) { // 若该字符的子节点不存在新建节点 tr[cur][path] idx; } cur tr[cur][path]; // 移动到子节点 p[cur]; // 该节点的前缀计数1 } } // 查询文本串s作为前缀的模式串数量 int find_pre(string s) { int cur 0; // 从根节点开始 for (char ch : s) { int path get_num(ch); if (tr[cur][path] 0) { // 路径中断无匹配的前缀 return 0; } cur tr[cur][path]; // 移动到子节点 } return p[cur]; // 返回最终节点的前缀计数 } int main() { ios::sync_with_stdio(false); // 加速cin/cout cin.tie(nullptr); int T; cin T; while (T--) { // 处理多组测试数据 // 清空字典树只清空用到的节点避免memset超时 for (int i 0; i idx; i) { memset(tr[i], 0, sizeof(tr[i])); // 清空当前节点的所有子节点 p[i] 0; // 清空计数 } idx 0; // 重置节点计数器 int n, q; cin n q; // 插入n个模式串 while (n--) { string s; cin s; insert(s); } // 处理q次查询 while (q--) { string s; cin s; cout find_pre(s) \n; } } return 0; }4.2于是他错误的点名开始了题⽬来源 洛⾕题⽬链接P2580 于是他错误的点名开始了难度系数 ★★题目背景XS中学化学竞赛组教练是一个酷爱炉石的人。他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉详情请见已结束比赛 CON900。题目描述这之后校长任命你为特派探员每天记录他的点名。校长会提供化学竞赛学生的人数和名单而你需要告诉校长他有没有点错名。为什么不直接不让他玩炉石。输入格式第一行一个整数 n表示班上人数。接下来 n 行每行一个字符串表示其名字互不相同且只含小写字母长度不超过 50。第 n2 行一个整数 m表示教练报的名字个数。接下来 m 行每行一个字符串表示教练报的名字只含小写字母且长度不超过 50。输出格式对于每个教练报的名字输出一行。如果该名字正确且是第一次出现输出OK如果该名字错误输出WRONG如果该名字正确但不是第一次出现输出REPEAT。输入输出样例输入 #1复制5 a b c ad acd 3 a a e输出 #1复制OK REPEAT WRONG说明/提示对于 40% 的数据n≤1000m≤2000。对于 70% 的数据n≤104m≤2×104。对于 100% 的数据n≤104m≤105。upd 2022.7.30新增加一组 Hack 数据。【解法】⽤字典树维护字符串当查询之后将 e 数组修改成 -1 即可【参考代码】#include iostream #include string using namespace std; // 字典树最大节点数根据实际数据量调整5e5足够应对大部分场景 const int N 5e5 10; // n学生名字数量m点名查询次数 int n, m; // tr[i][j]第i个节点的第j个小写字母0-25指向的子节点编号 // e[i]节点状态0非名字结尾0名字结尾且未查询-1名字结尾且已查询 int tr[N][26], e[N], idx; // 插入名字到字典树 void insert(string s) { int cur 0; // 从根节点编号0开始 for (auto ch : s) { // 遍历名字的每个字符 int path ch - a; // 小写字母映射为0-25的路径 if (tr[cur][path] 0) { // 路径未创建则新建节点 tr[cur][path] idx; } cur tr[cur][path]; // 移动到子节点 } e[cur]; // 标记该节点为名字结尾初始为未查询状态 } // 查询名字状态0不存在0首次查询-1重复查询 int find(string s) { int cur 0; // 从根节点开始 for (auto ch : s) { // 遍历查询名字的每个字符 int path ch - a; if (tr[cur][path] 0) { // 路径不存在名字不在名单中 return 0; } cur tr[cur][path]; // 移动到子节点 } // 路径存在判断节点状态 if (e[cur] 0) { int t e[cur]; e[cur] -1; // 标记为已查询 return t; } return e[cur]; // 返回-1重复查询 } int main() { // 优化输入输出速度大数据量必备 ios::sync_with_stdio(false); cin.tie(nullptr); // 输入学生名字数量并插入所有名字 cin n; while (n--) { string s; cin s; insert(s); } // 输入查询次数并处理所有点名查询 cin m; while (m--) { string s; cin s; int ret find(s); if (ret 0) { cout WRONG endl; } else if (ret 0) { cout OK endl; } else { cout REPEAT endl; } } return 0; }4.3最⼤异或对题⽬来源 洛⾕题⽬链接P10471 最⼤异或对 The XOR Largest Pair难度系数 ★★★题目描述给定 N 个整数 A1​.A2​,⋯,AN​ 中选出两个进行异或计算得到的结果最大是多少输入格式第一行一个整数 N第二行 N 个整数 A1​.A2​,⋯,AN​。输出格式一个整数表示答案。输入输出样例输入 #1复制3 1 2 3输出 #1复制3说明/提示对于所有测试数据1≤N≤105保证 0≤Ai​231。【解法】将所有数按照⼆进制位存在字典树中针对每⼀个数x按照⼆进制匹配最优的⽅案。【参考代码】#include iostream using namespace std; const int N 1e5 10; int n; int a[N]; // 字典树每个数32位1e5个数最多需要1e5*32个节点 int tr[N * 32][2], idx; // 插入数字x的二进制到字典树从高位到低位 void insert(int x) { int cur 0; for (int i 31; i 0; i--) { // 取出x的第i位二进制值0/1 int path ((x i) 1); // 路径不存在则新建节点 if (tr[cur][path] 0) tr[cur][path] idx; // 移动到子节点 cur tr[cur][path]; } } // 找和x异或最大的数返回异或结果 int find(int x) { int cur 0; int ret 0; for (int i 31; i 0; i--) { int path ((x i) 1); // 优先走相反的位贪心 if (tr[cur][path ^ 1]) { ret | (1 i); // 异或结果的第i位设为1 cur tr[cur][path ^ 1]; } else { // 无相反位走相同位 cur tr[cur][path]; } } return ret; } int main() { cin n; for (int i 1; i n; i) { cin a[i]; insert(a[i]); } int ret 0; for (int i 1; i n; i) { ret max(ret, find(a[i])); } cout ret endl; return 0; }