Acwing - 算法基础课 - 笔记（五） 约定不等于承诺〃 2022-10-06 04:59 151阅读 0赞 ### 文章目录 ### * * 数据结构（二） * * Trie树 * * 练习题：\[Acwing - 835: Trie字符串统计\](https://www.acwing.com/problem/content/837/) * 课后题：\[Acwing - 143: 最大异或对\](https://www.acwing.com/problem/content/145/) * 并查集 * * 练习题：\[Acwing - 836: 合并集合\](https://www.acwing.com/problem/content/838)（裸并查集，不带任何额外信息） * 课后题：\[Acwing - 837: 连通块中点的数量\](https://www.acwing.com/problem/content/839)（额外维护集合中元素的个数） * 课后题（hard）：\[Acwing - 240: 食物链\](https://www.acwing.com/problem/content/242/) * 堆 * * 练习题：\[Acwing - 838: 堆排序\](https://www.acwing.com/problem/content/description/840/) * 练习题：\[Acwing - 839: 模拟堆\](https://www.acwing.com/problem/content/description/841/) ## 数据结构（二） ## 本节讲解的内容是，Trie树（字典树），并查集，堆（Dijkstra算法可以使用堆进行优化） ### Trie树 ### Trie树，又称字典树，是用来**高效存储和查找字符串集合**的一种数据结构 查找时，可以高效的查找某个字符串是否在Trie树中出现过，并且可以查找出现了多少次 其逻辑结构如下 假设我们需要维护一个字符串集合，它需要支持两种操作 * 向集合插入一个字符串`x` * 查询一个字符串在集合中出现了多少次 假设我们有一个字符串集合，包含如下的字符串 `abcd`，`abc`，`aced`，`bbac`，`abde`，`bcac` 将这些字符串依次进行插入，构建出来的Trie树逻辑结构如下 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70][] 其中红色的节点表示，存在一个以该节点为结尾的字符串 #### 练习题：[Acwing - 835: Trie字符串统计][Acwing - 835_ Trie] #### #include<iostream> #include<string> using namespace std; const int N = 1e5 + 10; int q[N][26]; int ctn[N]; // 用来计数 int idx; // 用来分配新的节点 // 注意这里, 使用数组来模拟指针的 // 下标为0的节点, 既是根节点，也用来表示空节点 // 如一个节点下标为1，则q[1][0]表示这个节点的a儿子，若q[1][0] = 0, 表示1这个节点没有a儿子(空节点)，若q[1][0] = x , x不为0, 则表明1这个节点有a儿子，且a儿子的节点下标为x // 更通俗地讲, q[i][j]，表示了一个节点i连接其儿子节点的边，而j属于0~25, 表示了26个小写字母，当q[i][j] = x，且x不为0时，表明i这个节点有一儿子节点为某个字母, 且这个儿子节点下标为x //ctn[i], 表示以节点i为结尾的字符串, 出现了多少次 void insert(string s) { int p = 0; for(int i = 0; i < s.size(); i++) { int u = s[i] - 'a'; if(q[p][u] == 0) q[p][u] = ++idx; p = q[p][u]; // 更新当前节点 } ctn[p]++; } int query(string s) { int p = 0; for(int i = 0; i < s.size(); i++) { int u = s[i] - 'a'; if(q[p][u] == 0) return 0; // 不存在该节点 p = q[p][u]; } return ctn[p]; } int main() { int n; char op; string s; scanf("%d", &n); while(n--) { cin >> op >> s; if(op == 'I') { insert(s); } else if(op == 'Q') { int c = query(s); printf("%d\n", c); } } return 0; } #### 课后题：[Acwing - 143: 最大异或对][Acwing - 143_] #### 先想一个暴力做法，两层循环，穷举所有组合 int res = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) res = max(res, a[i] ^ a[j]); } 上面的代码中，有两层循环，其中，内层循环的含义是：对于当前已经固定的`a[i]`，在`[0,i)`之间找到一个`j`，使得`a[j] ^ a[i]`最大。 然而，对于内层循环，可以用Trie树优化，我们知道Trie树存的是字符串的集合，在这道题的场景下，我们考虑让Trie树来存储每个数字的二进制表示（二进制串）。每插入一个数到Trie树，从Trie树的根节点开始往下，先存这个数的二进制最高位，一直到叶子节点，存这个数的最低位。然后对于每一个`a[i]`，从其二进制的高位开始，在Trie树中查找，每次尝试找与`a[i]`当前位不同的分支节点，一直找下去，找到叶子节点，这个二进制串代表的数，就是与`a[i]`做异或最大的数。代码题解如下： #include<iostream> using namespace std; const int N = 1e5 + 10, M = 31 * N; // N 是数的个数上限, M是Trie树中节点个数的上限 // 由于每个二进制位,要么是0, 要么是1, 所以这个trie树是个二叉树 int son[M][2]; // 这个数组, 用来存Trie树 // 注意Trie树的节点个数不是N, 而是大于N的, 每个数最多有31个二进制位, 那么Trie树中总的节点数我们开大一些, 开为 31 * N int n, idx; // n 是数的个数, idx用来分配Trie树的节点下标 int q[N]; // 用来存输入的数 // 插入一个数到Trie树中 void insert(int x) { int p = 0; // 从根节点开始 // 从数字二进制表示的最高位开始插入 for(int i = 30; i >= 0; i--) { // 由于x的大小不超过2^31, 所以x的二进制表示最多31位 // 也就是0-30, 从最高位第31位开始, 即下标30 int u = (x >> i) & 1; //取这一位的二进制位 if(son[p][u] == 0) son[p][u] = ++idx; p = son[p][u]; } } // 查找和x做异或, 结果最大的值 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]) u = !u; // 若存在与x当前位相反的分支, 则走过去, 否则保持原样 p = son[p][u]; res = (res << 1) + u; // 计算这个最后的结果值 } return res; } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &q[i]); int res = 0; for(int i = 0; i < n; i++) { insert(q[i]); // 先插入当前的数q[i]到Trie树中 int x = query(q[i]); // 此时Trie树中存的是全部 j = [0,i)的全部q[j]的二进制串 // 这里相当于从[0,i)找与a[i]异或结果最大的那个数 res = max(res, q[i] ^ x); // 更新结果 } printf("%d", res); return 0; } 这道题，让我们知道，Trie树不仅可以存储字符串，还可以用来存储数字（二进制数） ### 并查集 ### 并查集结构能够支持快速进行如下的操作 1. **将两个集合合并** 2. **询问两个元素是否在一个集合当中** 并查集可以在近乎O(1)的时间复杂度下，完成上述2个操作 并查集的基本原理：**用树的形式来维护一个集合**。用树的根节点来代表这个集合。对于树中的每个节点，都存储其父节点的编号。比如一个节点编号为x，我们用p\[x\]来表示其父节点的编号 当我们想求，某一个节点所属的集合时，找到其父节点，并一直往上找，直到找到根节点，则根节点的编号，就是该节点所属的集合的编号。 问题1：如何判断根节点？ 对于根节点x，我们设置p\[x\] = x。那么，可以用p\[x\] == x 来判断是否是根节点 问题2：如何求某个节点x所属的集合编号？ `while(p[x] != x) x = p[x];` 一直向上走，直到找到根节点 问题3：如何合并2个集合？ 直接将一个集合作为另一个集合根节点的一个儿子节点即可。 假设一个A集合的根节点编号为x，另一个B集合根节点编号为y，则合并操作就是p\[x\] = y。即，将A集合的根节点作为B集合根节点的一个儿子。即，将A集合直接插到B集合里面。 对于查找某个节点x的所属集合，时间复杂度一开始可能没有O(1)，可能需要O(logn)，如果是二叉树的话。但可以采用**路径压缩**进行优化，当搜索完某个节点的所属集合时，直接将搜索路径上的所有节点的父节点，直接指向根节点，这样下次查询时就是O(1)。 并查集还有一种优化方式是**按秩合并**，大概是说的，将两个集合合并时，将高度较矮的那棵树，接到高度较高的树下面，具体的yxc没讲，这种优化用的比较少，而且好像也没有很有用 #### 练习题：[Acwing - 836: 合并集合][Acwing - 836_]（裸并查集，不带任何额外信息） #### #include<iostream> using namespace std; const int N = 1e5 + 10; int n, m; int p[N]; //存每个节点的父亲节点编号 int find(int x) { if(p[x] != x) p[x] = find(p[x]); // 路径压缩, 递归方式, 可能会由于递归过深而栈溢出 return p[x]; } int find2(int x) { int r = x; while(p[r] != r) r = p[r]; // 先找到根 // 再通过迭代循环的方式进行路径压缩 int t; while(p[x] != x) { t = x; x = p[x]; p[t] = r; } return r; } int main() { scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) p[i] = i; // 初始化 while(m--) { char op[2]; int a, b; scanf("%s%d%d", op, &a, &b); if(op[0] == 'M') { p[find(a)] = find(b); } else if(op[0] == 'Q') { if(find(a) == find(b)) printf("Yes\n"); else printf("No\n"); } } return 0; } #### 课后题：[Acwing - 837: 连通块中点的数量][Acwing - 837_]（额外维护集合中元素的个数） #### #include<iostream> #include<string> using namespace std; const int N = 1e5 + 10; int n, m; int p[N], ctn[N]; int find(int x) { if(p[x] != x) p[x] = find(p[x]); return p[x]; } int main() { scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) { p[i] = i; // 初始化 ctn[i] = 1; } while(m--) { string op; int a, b; cin >> op; if(op == "C") { cin >> a >> b; if(find(a) == find(b)) continue; // 特判一下，若同属一个集合, 后续操作不用再进行 ctn[find(b)] += ctn[find(a)]; // 将b集合的元素个数加上a的元素个数, 要先加, 再把a接到b p[find(a)] = find(b); // 将a接到b } else if(op == "Q1") { cin >> a >> b; if(find(a) == find(b)) printf("Yes\n"); else printf("No\n"); } else if(op == "Q2") { cin >> a; printf("%d\n", ctn[find(a)]); } } return 0; } #### 课后题（hard）：[Acwing - 240: 食物链][Acwing - 240_] #### （并查集的变形，可以额外维护每个节点到根节点的距离） 维护每个点到根节点的距离，用不同的距离来表示不同种类的动物。每个点到根节点的距离模3余0，表示是1类，模3余1，表示是2类，模3余2，表示是3类。其中，2类吃1类，3类吃2类，1类吃3类。 #include<iostream> using namespace std; const int N = 5e4 + 10; int n, m; int p[N], d[N]; // parent distance int find(int x) { if(p[x] != x) { int t = find(p[x]); d[x] += d[p[x]]; p[x] = t; } return p[x]; } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) p[i] = i; int res = 0; while(m--) { int t, x, y; scanf("%d%d%d", &t, &x, &y); if(x > n || y > n) res++; else { int px = find(x), py = find(y); if(t == 1) { if(px == py && (d[x] - d[y]) % 3) res++; else if(px != py) { p[px] = py; d[px] = d[y] - d[x]; } } else { if(px == py && (d[x] - d[y] - 1) % 3) res++; else if(px != py) { p[px] = py; d[px] = d[y] + 1 - d[x]; } } } } printf("%d", res); return 0; } **小结** 并查集最核心的部分，就是记录每个节点的父节点的数组`p[]`，以及查找某个节点所属的树的根节点的函数`find()`，以及路径压缩 初始化使得全部`p[i] = i`，表示每个点都是一个独立的集合。 合并时直接将一个集合的根节点，直接接入到另一个集合的根节点下面即可，即`p[find(a)] = find(b)` 核心就是找到某个节点所属的树的根节点 int find(int x) { if(p[x] != x) p[x] = find(p[x]); // 路径压缩 return p[x]; } ### 堆 ### 堆的基本操作（以小根堆为例） 1. **插入一个数** 2. **求集合当中的最小值** 3. **删除最小值** 4. 删除任意一个元素 5. 修改任意一个元素 堆的基本结构是一颗完全二叉树。以小根堆为例，每个节点都要小于其左右两个子树种的所有节点。 通常用数组来模拟存储一颗二叉树，采用二叉树层序遍历的方式作为数组的下标。若数组下标从0开始，若某个节点下标为x，则其左儿子下标为2x + 1，其右儿子下标为2x + 2。若数组下标从1开始，若某个节点下标为x，则其左儿子下标为2x，右儿子下标为2x + 1。 堆通过**向下调整**（down）和**向上调整**（up）来维持堆的特性。 down操作用来将一个较大的数，下沉到合适的位置 up操作用来将一个较小的数，上浮到合适的位置 可以通过down和up操作，完成上述的5个堆的基本操作（数组下标从1开始） 1. **插入一个数** 插入到数组末尾，并对于新插入的这个数，向上调整 `heap[++size] = x; up(size);` 2. **求集合当中的最小值** 直接返回堆顶，即数组的首元素 `heap[1]` 3. **删除最小值** 先交换堆顶和堆尾，然后堆的大小减一，再针对新的堆顶，向下调整 `swap(heap[1], heap[size]); size--; down(1)` 4. 删除任意一个元素 交换当前元素和堆尾，然后堆的大小减一，再根据新的当前元素的大小，决定是做down操作还是做up操作 `swap(heap[i], heap[size]); size--; down(i) 或者 up(i)` 5. 修改任意一个元素 直接修改，并且根据修改后的新值，来决定做down还是up `heap[i] = x; down(i) 或者 up(i)` 建堆，可以从堆尾往上，找到第一个非叶子节点，从第一个非叶子节点往前，对所有的非叶子节点，依次执行down操作。这样，**建堆的时间复杂度是O(n)**。 若数组下标从1开始，且堆总共有n个元素，则从后往前，第一个非叶子节点的下标为n/2。 #### 练习题：[Acwing - 838: 堆排序][Acwing - 838_] #### #include<iostream> using namespace std; const int N = 1e5 + 10; int h[N], hs; int n, m; // 堆的下标从1开始 void down(int x) { int min = x; if(2 * x <= hs && h[2 * x] < h[min]) min = 2 * x; if(2 * x + 1 <= hs && h[2 * x + 1] < h[min]) min = 2 * x + 1; if(min != x) { swap(h[min], h[x]); // 需要调整 down(min); // 递归调整 } } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &h[i]); hs = n; for(int i = n / 2; i >= 1; i--) down(i); // 这个建堆过程实际的时间复杂度是O(n) while(m--) { printf("%d ", h[1]); swap(h[1], h[hs]); hs--; down(1); } return 0; } 堆的两个基本操作：down和up // u是往下调整的节点下标 void down(int u) { int t = u; if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2; if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if(u != t) { swap(h[u], h[t]); down(t); // 因为最多是logn的复杂度, 可以直接用递归, 不用担心溢出 } } void up(int u) { while(u / 2 > 0 && h[u / 2] > h[u]) { swap(h[u / 2], h[u]); u /= 2; } } #### 练习题：[Acwing - 839: 模拟堆][Acwing - 839_] #### #include<iostream> #include<string> using namespace std; const int N = 1e5 + 10; int h[N], ph[N], hp[N]; // ph[i] = k 表示第i个插入的数, 在堆中的节点的下标是k // hp[k] = i 表示堆中下标为k的节点，是第i个插入的 int hSize, n; void heap_swap(int i, int j) { swap(ph[hp[i]], ph[hp[j]]); swap(hp[i], hp[j]); swap(h[i], h[j]); } void down(int i) { int min = i; int leftSon = 2 * i; if(leftSon <= hSize && h[leftSon] < h[min]) min = leftSon; if(leftSon + 1 <= hSize && h[leftSon + 1] < h[min]) min = leftSon + 1; if(min != i) { heap_swap(i, min); down(min); } } void up(int i) { while(i > 1 && h[i] < h[i / 2]) { heap_swap(i, i / 2); i /= 2; } } int main() { scanf("%d", &n); string op; int x, k; int insertCnt = 0; for(int i = 1; i <= n; i++) { cin >> op; if(op == "I") { scanf("%d", &x); h[++hSize] = x; ph[++insertCnt] = hSize; hp[hSize] = insertCnt; up(hSize); } else if(op == "PM") { printf("%d\n", h[1]); } else if(op == "DM") { heap_swap(1, hSize--); down(1); } else if(op == "D") { scanf("%d", &k); int hPos = ph[k]; heap_swap(hPos, hSize--); down(hPos); up(hPos); } else if(op == "C") { scanf("%d%d", &k, &x); int hPos = ph[k]; h[hPos] = x; down(hPos); up(hPos); } } return 0; } [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70]: /images/20221005/f49ccb86f37b48db9bea1c2199926e3e.png [Acwing - 835_ Trie]: https://www.acwing.com/problem/content/837/ [Acwing - 143_]: https://www.acwing.com/problem/content/145/ [Acwing - 836_]: https://www.acwing.com/problem/content/838 [Acwing - 837_]: https://www.acwing.com/problem/content/839 [Acwing - 240_]: https://www.acwing.com/problem/content/242/ [Acwing - 838_]: https://www.acwing.com/problem/content/description/840/ [Acwing - 839_]: https://www.acwing.com/problem/content/description/841/
相关 Acwing - 算法基础课 - 笔记（五） 文章目录 数据结构（二） Trie树 练习题：\[Acwing - 835: Trie字符串统计\](http 约定不等于承诺〃/ 2022年10月06日 04:59/ 0 赞/ 152 阅读
冷不防
àì夳堔傛蜴生んèń
今天药忘吃喽~
还没有评论，来说两句吧...