From 88926f996c22a5e34d8a83486751583cfc62f49a Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Fri, 1 Jan 2021 22:02:27 -0500 Subject: [PATCH] style: format markdown files with remark-lint --- docs/basic/binary-lifting.md | 1 - docs/basic/binary.md | 8 +-- docs/basic/divide-and-conquer.md | 21 +++---- docs/basic/prefix-sum.md | 10 +--- docs/basic/simulate.md | 2 - docs/contest/construction.md | 11 ++-- docs/ds/binary-heap.md | 120 ++++++++++++++++++++------------------- docs/ds/bit-in-block-array.md | 14 ++--- docs/ds/li-chao-tree.md | 6 +- docs/ds/queue.md | 18 +++--- docs/geometry/nearest-points.md | 2 +- docs/graph/euler.md | 2 - docs/graph/flow/max-flow.md | 29 +++++----- docs/graph/mdst.md | 62 ++++++++------------ docs/graph/mst.md | 1 + docs/graph/shortest-path.md | 8 +-- docs/math/linear-equation.md | 1 - docs/math/matrix.md | 5 +- docs/math/mobius.md | 2 +- docs/math/pollard-rho.md | 2 +- docs/math/poly/lagrange.md | 37 ++++++------ docs/math/prime.md | 4 +- docs/misc/mo-algo.md | 36 ++++++------ docs/misc/rand-technique.md | 48 ++++++++-------- docs/search/astar.md | 3 - docs/search/bidirectional.md | 3 +- docs/search/heuristic.md | 1 - docs/string/manacher.md | 10 ++-- docs/tools/editor/vscode.md | 2 +- 29 files changed, 222 insertions(+), 247 deletions(-) diff --git a/docs/basic/binary-lifting.md b/docs/basic/binary-lifting.md index 1f1e60f3..525112d5 100644 --- a/docs/basic/binary-lifting.md +++ b/docs/basic/binary-lifting.md @@ -38,7 +38,6 @@ RMQ 是 Range Maximum/Minimum Query 的缩写，表示区间最大（最小） 数据范围： $1\leq n\leq 10^6$ , $1\leq m\leq 10^{18}$ , $1\leq k\leq n$ , $0\le a_i\le 10^9$ 。 ??? note "解题思路" - 这里显然不能暴力模拟跳 $m$ 次。因为 $m$ 最大可到 $10^{18}$ 级别，如果暴力模拟的话，时间承受不住。 所以就需要进行一些预处理，提前整合一些信息，以便于在查询的时候更快得出结果。如果记录下来每一个可能的跳跃次数的结果的话，不论是时间还是空间都难以承受。 diff --git a/docs/basic/binary.md b/docs/basic/binary.md index 8ea85acf..876a913e 100644 --- a/docs/basic/binary.md +++ b/docs/basic/binary.md @@ -75,11 +75,11 @@ C++ 标准库中实现了查找首个不小于给定值的元素的函数 [ `std ???+note "[Luogu P1873 砍树](https://www.luogu.com.cn/problem/P1873)" 伐木工人米尔科需要砍倒 M 米长的木材。这是一个对米尔科来说很容易的工作，因为他有一个漂亮的新伐木机，可以像野火一样砍倒森林。不过，米尔科只被允许砍倒单行树木。 - 米尔科的伐木机工作过程如下：米尔科设置一个高度参数H（米），伐木机升起一个巨大的锯片到高度H，并锯掉所有的树比H高的部分（当然，树木不高于H米的部分保持不变）。米尔科就行到树木被锯下的部分。 + 米尔科的伐木机工作过程如下：米尔科设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，并锯掉所有的树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。米尔科就行到树木被锯下的部分。 - 例如，如果一行树的高度分别为20，15，10和17，米尔科把锯片升到15米的高度，切割后树木剩下的高度将是15，15，10和15，而米尔科将从第1棵树得到5米，从第4棵树得到2米，共得到7米木材。 + 例如，如果一行树的高度分别为 20，15，10 和 17，米尔科把锯片升到 15 米的高度，切割后树木剩下的高度将是 15，15，10 和 15，而米尔科将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。 - 米尔科非常关注生态保护，所以他不会砍掉过多的木材。这正是他为什么尽可能高地设定伐木机锯片的原因。帮助米尔科找到伐木机锯片的最大的整数高度H，使得他能得到木材至少为M米。换句话说，如果再升高1米，则他将得不到M米木材。 + 米尔科非常关注生态保护，所以他不会砍掉过多的木材。这正是他为什么尽可能高地设定伐木机锯片的原因。帮助米尔科找到伐木机锯片的最大的整数高度 H，使得他能得到木材至少为 M 米。换句话说，如果再升高 1 米，则他将得不到 M 米木材。 ??? note "解题思路" 我们可以在 1 到 1,000,000,000（10 亿）中枚举答案，但是这种朴素写法肯定拿不到满分，因为从 1 跑到 10 亿太耗时间。我们可以对答案进行 1 到 10 亿的二分，然后，每次都对其进行检查可行性（一般都是使用贪心法）。 **这就是二分答案。** @@ -118,7 +118,7 @@ C++ 标准库中实现了查找首个不小于给定值的元素的函数 [ `std 看完了上面的代码，你肯定会有两个疑问： - 1. 为何搜索区间是左闭右开的？ + 1. 为何搜索区间是左闭右开的？ 因为搜到最后，会这样（以合法的最大值为例）： diff --git a/docs/basic/divide-and-conquer.md b/docs/basic/divide-and-conquer.md index 1ca83e7b..37ebad36 100644 --- a/docs/basic/divide-and-conquer.md +++ b/docs/basic/divide-and-conquer.md @@ -166,14 +166,13 @@ void traverse(TreeNode* root) { ## 例题详解 ???+note "[437. 路径总和 III](https://leetcode-cn.com/problems/path-sum-iii/)" - 给定一个二叉树，它的每个结点都存放着一个整数值。 找出路径和等于给定数值的路径总数。 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 - 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。 + 二叉树不超过 1000 个节点，且节点数值范围是[-1000000,1000000]的整数。 示例： @@ -194,16 +193,17 @@ void traverse(TreeNode* root) { 2. 5 -> 2 -> 1 3. -3 -> 11 ``` + ```cpp /** - * 二叉树结点的定义 - * struct TreeNode { - * int val; - * TreeNode *left; - * TreeNode *right; - * TreeNode(int x) : val(x), left(NULL), right(NULL) {} - * }; - */ + * 二叉树结点的定义 + * struct TreeNode { + * int val; + * TreeNode *left; + * TreeNode *right; + * TreeNode(int x) : val(x), left(NULL), right(NULL) {} + * }; + */ ``` ??? note "参考代码" @@ -242,6 +242,7 @@ void traverse(TreeNode* root) { pathSum(root->right, sum); // 右边路径总数（相信它能算出来） return leftPathSum + rightPathSum + pathImLeading; } + ``` int count(TreeNode *node, int sum) { if (node == nullptr) return 0; diff --git a/docs/basic/prefix-sum.md b/docs/basic/prefix-sum.md index fd6464ae..6826906d 100644 --- a/docs/basic/prefix-sum.md +++ b/docs/basic/prefix-sum.md @@ -24,7 +24,6 @@ C++ 标准库中实现了前缀和函数 [ `std::partial_sum` ](https://zh.cppre ``` ??? note "解题思路" - 对于这道题，我们有两种做法： - 把对数组 A 的累加依次放入数组 B 中。 @@ -63,7 +62,6 @@ C++ 标准库中实现了前缀和函数 [ `std::partial_sum` ](https://zh.cppre 多维前缀和的普通求解方法几乎都是基于容斥原理。 ???+note "示例：一维前缀和扩展到二维前缀和" - 比如我们有这样一个矩阵 $a$ ，可以视为二维数组： ```text @@ -92,8 +90,7 @@ C++ 标准库中实现了前缀和函数 [ `std::partial_sum` ](https://zh.cppre #### 例题 ???+note "[洛谷 P1387 最大正方形](https://www.luogu.com.cn/problem/P1387)" - - 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。 + 在一个 n\*m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形，输出边长。 ??? note "参考代码" ```cpp @@ -173,14 +170,13 @@ C++ 标准库中实现了前缀和函数 [ `std::partial_sum` ](https://zh.cppre 它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。 ???+note "示例" - 譬如使 $[l,r]$ 中的每个数加上一个 $k$ ，就是 $$ b_l \leftarrow b_l + k,b_{r + 1} \leftarrow b_{r + 1} - k $$ - 其中 $b_l+k=a_l+k-a_{l-1}$ , $b_{r+1}-k=a_{r+1}-(a_r+k)$ + 其中 $b_l+k=a_l+k-a_{l-1}$ , $b_{r+1}-k=a_{r+1}-(a_r+k)$ 最后做一遍前缀和就好了。 @@ -234,7 +230,7 @@ $$ ???+note "[洛谷 3128 最大流](https://www.luogu.com.cn/problem/P3128)" FJ 给他的牛棚的 $N(2 \le N \le 50,000)$ 个隔间之间安装了 $N-1$ 根管道，隔间编号从 $1$ 到 $N$ 。所有隔间都被管道连通了。 - FJ有 $K(1 \le K \le 100,000)$ 条运输牛奶的路线，第 $i$ 条路线从隔间 $s_i$ 运输到隔间 $t_i$ 。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。 + FJ 有 $K(1 \le K \le 100,000)$ 条运输牛奶的路线，第 $i$ 条路线从隔间 $s_i$ 运输到隔间 $t_i$ 。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。 ??? note "解题思路" 需要统计每个点经过了多少次，那么就用树上差分将每一次的路径上的点加一，可以很快得到每个点经过的次数。这里采用倍增法进行 lca 的计算。最后对 DFS 遍历整棵树，在回溯时对差分数组求和就能求得答案了。 diff --git a/docs/basic/simulate.md b/docs/basic/simulate.md index 37882a73..526b1eeb 100644 --- a/docs/basic/simulate.md +++ b/docs/basic/simulate.md @@ -21,11 +21,9 @@ ## 例题详解 ???+note " [Climbing Worm - HDU](http://acm.hdu.edu.cn/showproblem.php?pid=1049)" - 一只一英寸的蠕虫位于 n 英寸深的井的底部。它每分钟向上爬 u 英寸，但是必须休息一分钟才能再次向上爬。在休息的时候，它滑落了 d 英寸。之后它将重复向上爬和休息的过程。蠕虫爬出井口花费了多长时间？我们将不足一分钟的部分算作一整分钟。如果蠕虫爬完后刚好到达井的顶部，我们也设作蠕虫已经爬出井口。 ??? note "解题思路" - 直接使用程序模拟蠕虫爬井的过程就可以了。用一个循环重复蠕虫的爬井过程，当攀爬的长度超过或者等于井的深度时跳出。注意上爬和下滑时都要递增时间。 ??? note "参考代码" diff --git a/docs/contest/construction.md b/docs/contest/construction.md index b4250b1e..0ed252e3 100644 --- a/docs/contest/construction.md +++ b/docs/contest/construction.md @@ -21,7 +21,6 @@ ### 例题 1 ???+note "[Codeforces Round #384 (Div. 2) C.Vladik and fractions](http://codeforces.com/problemset/problem/743/C)" - 构造一组 $x,y,z$ ，使得对于给定的 $n$ ，满足 $\dfrac{1}{x}+\dfrac{1}{y}+\dfrac{1}{z}=\dfrac{2}{n}$ ??? note "解题思路" @@ -34,10 +33,9 @@ ### 例题 2 ???+note "[Luogu P3599 Koishi Loves Construction](https://www.luogu.com.cn/problem/P3599)" + Task1：试判断能否构造并构造一个长度为 $n$ 的 $1\dots n$ 的排列，满足其 $n$ 个前缀和在模 $n$ 的意义下互不相同 - Task1：试判断能否构造并构造一个长度为$n$的$1\dots n$的排列，满足其$n$个前缀和在模$n$的意义下互不相同 - - Taks2：试判断能否构造并构造一个长度为$n$的$1\dots n$的排列，满足其$n$个前缀积在模$n$的意义下互不相同 + Taks2：试判断能否构造并构造一个长度为 $n$ 的 $1\dots n$ 的排列，满足其 $n$ 个前缀积在模 $n$ 的意义下互不相同 ??? note "解题思路" 对于 task1： @@ -79,11 +77,10 @@ ### 例题 3 ???+note "[AtCoder Grand Contest 032 B](https://atcoder.jp/contests/agc032/tasks/agc032_b)" - - You are given an integer $N$. Build an undirected graph with $N$ vertices with indices $1$ to $N$ that satisfies the following two conditions: + You are given an integer $N$ . Build an undirected graph with $N$ vertices with indices $1$ to $N$ that satisfies the following two conditions: - The graph is simple and connected. - - There exists an integer $S$ such that, for every vertex, the sum of the indices of the vertices adjacent to that vertex is $S$. + - There exists an integer $S$ such that, for every vertex, the sum of the indices of the vertices adjacent to that vertex is $S$ . It can be proved that at least one such graph exists under the constraints of this problem. diff --git a/docs/ds/binary-heap.md b/docs/ds/binary-heap.md index 129e3986..678188f8 100644 --- a/docs/ds/binary-heap.md +++ b/docs/ds/binary-heap.md @@ -129,13 +129,14 @@ $$ #### 对顶堆 ??? note "[SP16254 RMID2 - Running Median Again](https://www.luogu.com.cn/problem/SP16254)" - 维护一个序列，支持两种操作： - - 1. 向序列中插入一个元素 - - 2. 输出并删除当前序列的中位数（若序列长度为偶数，则输出较小的中位数） -这个问题可以被进一步抽象成：动态维护一个序列上第 $k$ 大的数，$k$ 值可能会发生变化。 + 维护一个序列，支持两种操作： + + 1. 向序列中插入一个元素 + + 2. 输出并删除当前序列的中位数（若序列长度为偶数，则输出较小的中位数） + +这个问题可以被进一步抽象成：动态维护一个序列上第 $k$ 大的数， $k$ 值可能会发生变化。 对于此类问题，我们可以使用 **对顶堆** 这一技巧予以解决（可以避免写权值线段树或 BST 带来的繁琐）。 @@ -143,62 +144,63 @@ $$ 这两个堆构成的数据结构支持以下操作： -- 维护：当大根堆的大小小于 $k$ 时，不断将小根堆堆顶元素取出并插入大根堆，直到大根堆的大小等于 $k$；当大根堆的大小大于 $k$ 时，不断将大根堆堆顶元素取出并插入小根堆，直到大根堆的大小等于 $k$； +- 维护：当大根堆的大小小于 $k$ 时，不断将小根堆堆顶元素取出并插入大根堆，直到大根堆的大小等于 $k$ ；当大根堆的大小大于 $k$ 时，不断将大根堆堆顶元素取出并插入小根堆，直到大根堆的大小等于 $k$ ； - 插入元素：若插入的元素小于等于大根堆堆顶元素，则将其插入大根堆，否则将其插入小根堆，然后维护对顶堆； - 查询第 $k$ 大元素：大根堆堆顶元素即为所求； - 删除第 $k$ 大元素：删除大根堆堆顶元素，然后维护对顶堆； -- $k$ 值 $+1/-1$ ：根据新的 $k$ 值直接维护对顶堆。 +- $k$ 值 $+1/-1$ ：根据新的 $k$ 值直接维护对顶堆。 -显然，查询第 $k$ 大元素的时间复杂度是 $O(1)$ 的。由于插入、删除或调整 $k$ 值后，大根堆的大小与期望的 $k$ 值最多相差 $1$，故每次维护最多只需对大根堆与小根堆中的元素进行一次调整，因此，这些操作的时间复杂度都是 $O(\log n)$ 的。 +显然，查询第 $k$ 大元素的时间复杂度是 $O(1)$ 的。由于插入、删除或调整 $k$ 值后，大根堆的大小与期望的 $k$ 值最多相差 $1$ ，故每次维护最多只需对大根堆与小根堆中的元素进行一次调整，因此，这些操作的时间复杂度都是 $O(\log n)$ 的。 ??? "参考代码" - ```cpp - #include - #include - #include - using namespace std; - int t, x; - int main() - { - scanf("%d", &t); - while (t--) - { - // 大根堆，维护前一半元素 - priority_queue, less > a; - // 小根堆，维护后一半元素 - priority_queue, greater > b; - while (scanf("%d", &x) && x) - { - // 若为查询并删除操作，输出并删除大根堆堆顶元素 - if (x == -1) - { - printf("%d\n", a.top()); - a.pop(); - } - // 若为插入操作，根据大根堆堆顶的元素值，选择合适的堆进行插入 - else - { - if (a.empty() || x <= a.top()) - a.push(x); - else - b.push(x); - } - // 对堆顶堆进行调整 - if (a.size() > (a.size() + b.size() + 1) / 2) - { - b.push(a.top()); - a.pop(); - } - else if (a.size() < (a.size() + b.size() + 1) / 2) - { - a.push(b.top()); - b.pop(); - } - } - } - return 0; - } - ``` - -- 双倍经验：[SP15376 RMID - Running Median](https://www.luogu.com.cn/problem/SP15376) -- 典型习题：[P1801 黑匣子](https://www.luogu.com.cn/problem/P1801) + + ```cpp + #include + #include + #include + using namespace std; + int t, x; + int main() + { + scanf("%d", &t); + while (t--) + { + // 大根堆，维护前一半元素 + priority_queue, less > a; + // 小根堆，维护后一半元素 + priority_queue, greater > b; + while (scanf("%d", &x) && x) + { + // 若为查询并删除操作，输出并删除大根堆堆顶元素 + if (x == -1) + { + printf("%d\n", a.top()); + a.pop(); + } + // 若为插入操作，根据大根堆堆顶的元素值，选择合适的堆进行插入 + else + { + if (a.empty() || x <= a.top()) + a.push(x); + else + b.push(x); + } + // 对堆顶堆进行调整 + if (a.size() > (a.size() + b.size() + 1) / 2) + { + b.push(a.top()); + a.pop(); + } + else if (a.size() < (a.size() + b.size() + 1) / 2) + { + a.push(b.top()); + b.pop(); + } + } + } + return 0; + } + ``` + +- 双倍经验： [SP15376 RMID - Running Median](https://www.luogu.com.cn/problem/SP15376) +- 典型习题： [P1801 黑匣子](https://www.luogu.com.cn/problem/P1801) diff --git a/docs/ds/bit-in-block-array.md b/docs/ds/bit-in-block-array.md index 7146481e..05a1b32c 100644 --- a/docs/ds/bit-in-block-array.md +++ b/docs/ds/bit-in-block-array.md @@ -9,10 +9,10 @@ ???+ note "矩形区域查询" 给出 $n$ 个二维平面中的点 $(x_i, y_i)$ ，其中 $1 \le i \le n, 1 \le x_i, y_i \le n, 1 \le n \le 10^5$ , 要求实现以下中操作： - 1. 给出$a, b, c, d$，询问以$(a, b)$为左上角， $c, d$为右下角的矩形区域内点的个数。 - 2. 给出$x, y$，将横坐标为$x$的点的纵坐标改为$y$。 + 1. 给出 $a, b, c, d$ ，询问以 $(a, b)$ 为左上角， $c, d$ 为右下角的矩形区域内点的个数。 + 2. 给出 $x, y$ ，将横坐标为 $x$ 的点的纵坐标改为 $y$ 。 - 题目**强制在线**，保证$x_i \ne x_j(1 \le i, j \le n, i \ne j)$。 + 题目 **强制在线** ，保证 $x_i \ne x_j(1 \le i, j \le n, i \ne j)$ 。 对于操作 1，可以通过矩形容斥将其转化为 4 个二维偏序的查询去解决，然后因为强制在线，CDQ 分治之类的离线算法就解决不了，于是想到了树套树，比如树状数组套 Treap。这确实可以解决这个问题，但是代码太长了，也不是特别好实现。 @@ -57,10 +57,10 @@ ???+ note " [Intersection of Permutations](https://codeforces.com/problemset/problem/1093/E) " 给出两个排列 $a$ 和 $b$ ，要求实现以下两种操作： - 1. 给出$l_a, r_a, l_b, r_b$，要求查询既出现在$a[l_a ... r_a]$又出现在$b[l_b ... r_b]$中的元素的个数。 - 2. 给出$x, y$，$swap(b_x, b_y)$。 + 1. 给出 $l_a, r_a, l_b, r_b$ ，要求查询既出现在 $a[l_a ... r_a]$ 又出现在 $b[l_b ... r_b]$ 中的元素的个数。 + 2. 给出 $x, y$ ， $swap(b_x, b_y)$ 。 - 序列长度$n$满足$2 \le n \le 2 \cdot 10^5$，操作个数$q$满足$1 \le q \le 2 \cdot 10^5$。 + 序列长度 $n$ 满足 $2 \le n \le 2 \cdot 10^5$ ，操作个数 $q$ 满足 $1 \le q \le 2 \cdot 10^5$ 。 对于每个值 $i$ ，记 $x_i$ 是它在排列 $b$ 中的下标， $y_i$ 是它在排列 $a$ 中的下标。这样，操作一就变成了一个矩形区域内点的个数的询问，操作 2 可以看成两个修改操作。而且因为是排列，所以满足一个 $x$ 对应一个 $y$ ，所以这题可以用分块套树状数组来写。 @@ -293,7 +293,7 @@ ???+ note " [Complicated Computations](https://codeforces.com/contest/1436/problem/E) " 给出一个序列 $a$ ，将 $a$ 所有连续子序列的 MEX 构成的数组作为 $b$ ，问 $b$ 的 MEX。一个序列的 MEX 是序列中最小的没出现过的 **正整数** 。 - 序列的长度$n$满足$1 \le n \le 10^5$。 + 序列的长度 $n$ 满足 $1 \le n \le 10^5$ 。 **观察** ：一个序列的 MEX 为 $mex$ ，当且仅当这个序列包含 $1$ 至 $mex-1$ ，但不包含 $mex$ 。 diff --git a/docs/ds/li-chao-tree.md b/docs/ds/li-chao-tree.md index 247274e1..765302da 100644 --- a/docs/ds/li-chao-tree.md +++ b/docs/ds/li-chao-tree.md @@ -3,10 +3,10 @@ ???+note "洛谷 4097 [HEOI2013]Segment" 要求在平面直角坐标系下维护两个操作（强制在线）： - 1. 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$，该线段的两个端点分别为 $(x_0,y_0)$，$(x_1,y_1)$。 - 2. 给定一个数 $k$，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号（若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段）。特别地，若不存在线段与给定直线相交，输出 $0$。 + 1. 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$ ，该线段的两个端点分别为 $(x_0,y_0)$ ， $(x_1,y_1)$ 。 + 2. 给定一个数 $k$ ，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号（若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段）。特别地，若不存在线段与给定直线相交，输出 $0$ 。 - 数据满足：操作总数 $1 \leq n \leq 10^5$，$1 \leq k, x_0, x_1 \leq 39989$，$1 \leq y_0, y_1 \leq 10^9$。 + 数据满足：操作总数 $1 \leq n \leq 10^5$ ， $1 \leq k, x_0, x_1 \leq 39989$ ， $1 \leq y_0, y_1 \leq 10^9$ 。 我们发现，传统的线段树无法很好地维护这样的信息。这种情况下， **李超线段树** 便应运而生。 diff --git a/docs/ds/queue.md b/docs/ds/queue.md index f70245af..ef1005d3 100644 --- a/docs/ds/queue.md +++ b/docs/ds/queue.md @@ -60,30 +60,28 @@ int q[SIZE], ql = 1, qr; ## 例题 ???+note "[LOJ6515「雅礼集训 2018 Day10」贪玩蓝月](https://loj.ac/problem/6515)" - 一个双端队列（deque），m 个事件： 1. 在前端插入 (w,v) 2. 在后端插入 (w,v) 3. 删除前端的二元组 4. 删除后端的二元组 - 5. 给定 l,r，在当前 deque 中选择一个子集 S 使得 $\sum_{(w,v)\in S}w\bmod p\in[l,r]$ ，且最大化 $\sum_{(w,v)\in S}v$ . + 5. 给定 l,r，在当前 deque 中选择一个子集 S 使得 $\sum_{(w,v)\in S}w\bmod p\in[l,r]$ ，且最大化 $\sum_{(w,v)\in S}v$ . - $m\leq 5\times 10^4,p\leq 500$ . + $m\leq 5\times 10^4,p\leq 500$ . ??? note "解题思路" - 每个二元组是有一段存活时间的，因此对时间建立线段树，每个二元组做 log 个存活标记。因此我们要做的就是对每个询问，求其到根节点的路径上的标记的一个最优子集。显然这个可以 DP 做。 $f[S,j]$ 表示选择集合 S 中的物品余数为 j 的最大价值。（其实实现的时侯是有序的，直接 f[i,j]做） 一共有 $O(m\log m)$ 个标记，因此这么做的话复杂度是 $O(mp\log m)$ 的。 - --- + * * * 这是一个在线算法比离线算法快的神奇题目。而且还比离线的好写。 上述离线算法其实是略微小题大做的，因为如果把题目的 deque 改成直接维护一个集合的话（即随机删除集合内元素），那么离线算法同样适用。既然是 deque，不妨在数据结构上做点文章。 - --- + * * * 如果题目中维护的数据结构是一个栈呢？ @@ -97,13 +95,13 @@ int q[SIZE], ql = 1, qr; 删除的时侯直接指针前移即可。这样做的复杂度是 $O(mp)$ 的。 - --- + * * * 如果题目中维护的数据结构是队列？ 有一种操作叫双栈模拟队列。这就是这个东西的用武之地。因为用栈是可以轻松维护 DP 过程的，而双栈模拟队列的复杂度是均摊 $O(1)$ 的，因此，复杂度仍是 $O(mp)$ 。 - --- + * * * 回到原题，那么 Deque 怎么做？ @@ -113,7 +111,7 @@ int q[SIZE], ql = 1, qr; 这样的复杂度其实均摊下来仍是常数级别。具体地说，丢一半指的是把一个栈靠近栈底的一半倒过来丢到另一个栈中。也就是说要手写栈以支持这样的操作。 - --- + * * * 似乎可以用 [势能分析法](https://yhx-12243.github.io/OI-transit/records/cf601E.html) 证明。其实本蒟蒻有一个很仙的想法。我们考虑这个双栈结构的整体复杂度。m 个事件，我们希望尽可能增加这个结构的复杂度。 @@ -133,7 +131,7 @@ int q[SIZE], ql = 1, qr; 于是，总复杂度仍是 $O(mp)$ 。 - --- + * * * 在询问的时侯，我们要处理的应该是“在两个栈中选若干个元素的最大价值”的问题。因此要对栈顶的 DP 值做查询，即两个 $f,g$ 对于询问[l,r]的最大价值： diff --git a/docs/geometry/nearest-points.md b/docs/geometry/nearest-points.md index 207166cf..274a3e54 100644 --- a/docs/geometry/nearest-points.md +++ b/docs/geometry/nearest-points.md @@ -213,7 +213,7 @@ $$ - [SPOJ #8725 CLOPPAIR "Closest Point Pair"\[难度：低\]](https://www.spoj.com/problems/CLOPPAIR/) - [CODEFORCES Team Olympiad Saratov - 2011 "Minimum amount"\[难度：中\]](http://codeforces.com/contest/120/problem/J) - [SPOJ #7029 CLOSEST "Closest Triple"\[难度：中\]](https://www.spoj.com/problems/CLOSEST/) -- [Google Code Jam 2009 Final "Min Perimeter"\[难度：中\]](https://codingcompetitions.withgoogle.com/codejam/round/0000000000432ad5/0000000000433195) +- [Google Code Jam 2009 Final "Min Perimeter"\[难度：中\]](https://codingcompetitions.withgoogle.com/codejam/round/0000000000432ad5/0000000000433195) * * * diff --git a/docs/graph/euler.md b/docs/graph/euler.md index 35439119..c0a28d6b 100644 --- a/docs/graph/euler.md +++ b/docs/graph/euler.md @@ -108,7 +108,6 @@ $$ ## 例题 ???+note "[洛谷 P2731 骑马修栅栏](https://www.luogu.com.cn/problem/P2731)" - 给定一张有 500 个顶点的无向图，求这张图的一条欧拉路或欧拉回路。如果有多组解，输出最小的那一组。 在本题中，欧拉路或欧拉回路不需要经过所有顶点。 @@ -116,7 +115,6 @@ $$ 边的数量 m 满足 $1\leq m \leq 1024$ 。 ??? note "解题思路" - 用 Fleury 算法解决本题的时候只需要再贪心就好，不过由于复杂度不对，还是换 Hierholzer 算法吧。 保存答案可以使用 `stack` ，因为如果找的不是回路的话必须将那一部分放在最后。 diff --git a/docs/graph/flow/max-flow.md b/docs/graph/flow/max-flow.md index 2a4436e8..a2de8c93 100644 --- a/docs/graph/flow/max-flow.md +++ b/docs/graph/flow/max-flow.md @@ -63,11 +63,11 @@ EK 算法的时间复杂度为 $O(nm^2)$ （其中 $n$ 为点数， $m$ 为边 }; struct EK { - int n, m; // n：点数，m：边数 - vector edges; // edges：所有边的集合 - vector G[maxn]; // G：点 x -> x 的所有边在 edges 中的下标 - int a[maxn], p[maxn]; // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流 - // p：点 x -> BFS 过程中最近接近点 x 的边 + int n, m; // n：点数，m：边数 + vector edges; // edges：所有边的集合 + vector G[maxn]; // G：点 x -> x 的所有边在 edges 中的下标 + int a[maxn], p[maxn]; // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流 + // p：点 x -> BFS 过程中最近接近点 x 的边 void init(int n) { for (int i = 0; i < n; i++) G[i].clear(); @@ -92,20 +92,23 @@ EK 算法的时间复杂度为 $O(nm^2)$ （其中 $n$ 为点数， $m$ 为边 while (!Q.empty()) { int x = Q.front(); Q.pop(); - for (int i = 0; i < G[x].size(); i++) { // 遍历以 x 作为起点的边 + for (int i = 0; i < G[x].size(); i++) { // 遍历以 x 作为起点的边 Edge& e = edges[G[x][i]]; if (!a[e.to] && e.cap > e.flow) { - p[e.to] = G[x][i]; // G[x][i] 是最近接近点 e.to 的边 - a[e.to] = min(a[x], e.cap - e.flow); // 最近接近点 e.to 的边赋给它的流 + p[e.to] = G[x][i]; // G[x][i] 是最近接近点 e.to 的边 + a[e.to] = + min(a[x], e.cap - e.flow); // 最近接近点 e.to 的边赋给它的流 Q.push(e.to); } } - if (a[t]) break; // 如果汇点接受到了流，就退出 BFS + if (a[t]) break; // 如果汇点接受到了流，就退出 BFS } - if (!a[t]) break; // 如果汇点没有接受到流，说明源点和汇点不在同一个连通分量上 - for (int u = t; u != s; u = edges[p[u]].from) { // 通过 u 追寻 BFS 过程中 s -> t 的路径 - edges[p[u]].flow += a[t]; // 增加路径上边的 flow 值 - edges[p[u] ^ 1].flow -= a[t]; // 减小反向路径的 flow 值 + if (!a[t]) + break; // 如果汇点没有接受到流，说明源点和汇点不在同一个连通分量上 + for (int u = t; u != s; + u = edges[p[u]].from) { // 通过 u 追寻 BFS 过程中 s -> t 的路径 + edges[p[u]].flow += a[t]; // 增加路径上边的 flow 值 + edges[p[u] ^ 1].flow -= a[t]; // 减小反向路径的 flow 值 } flow += a[t]; } diff --git a/docs/graph/mdst.md b/docs/graph/mdst.md index 8b78fc8e..82f52e83 100644 --- a/docs/graph/mdst.md +++ b/docs/graph/mdst.md @@ -43,49 +43,37 @@ 4. 图的绝对中心可能在某条边上，枚举所有的边。对于一条边 $w(u,j)$ 从距离 $u$ 最远的结点开始更新。当出现 $d(v,\textit{rk}(u,i)) > d(v,\textit{rk}(u,i-1))$ 的情况时，用 $\textit{ans}\leftarrow \min(\textit{ans}, d(v,\textit{rk}(u,i))+d(v,\textit{rk}(u,i-1))+w(i,j))$ 来更新。因为这种情况会使图的绝对中心改变。 ??? note "参考实现" - ```cpp - bool cmp(int a, int b) - { - return val[a] < val[b]; - } + bool cmp(int a, int b) { return val[a] < val[b]; } - void Floyd() - { - for (int k = 1; k <= n; k ++) - for (int i = 1; i <= n; i ++) - for (int j = 1; j <= n; j ++) - d[i][j] = min(d[i][j], d[i][k] + d[k][j]); + void Floyd() { + for (int k = 1; k <= n; k++) + for (int i = 1; i <= n; i++) + for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } - void solve() - { - Floyd(); - for (int i = 1; i <= n; i ++) - { - for (int j = 1; j <= n; j ++) - { - rk[i][j] = j; - val[j] = d[i][j]; - } - sort(rk[i] + 1, rk[i] + 1 + n, cmp); + void solve() { + Floyd(); + for (int i = 1; i <= n; i++) { + for (int j = 1; j <= n; j++) { + rk[i][j] = j; + val[j] = d[i][j]; } - int ans = INF; - // 图的绝对中心可能在结点上 - for (int i = 1; i <= n; i ++) ans = min(ans, d[i][rk[i][n]] * 2); - // 图的绝对中心可能在边上 - for (int i = 1; i <= m; i ++) - { - int u = a[i].u, v = a[i].v, w = a[i].w; - for (int p = n, i = n - 1; i >= 1; i --) - { - if (d[v][rk[u][i]] > d[v][rk[u][p]]) - { - ans = min(ans, d[u][rk[u][i]] + d[v][rk[u][p]] + w); - p = i; - } - } + sort(rk[i] + 1, rk[i] + 1 + n, cmp); + } + int ans = INF; + // 图的绝对中心可能在结点上 + for (int i = 1; i <= n; i++) ans = min(ans, d[i][rk[i][n]] * 2); + // 图的绝对中心可能在边上 + for (int i = 1; i <= m; i++) { + int u = a[i].u, v = a[i].v, w = a[i].w; + for (int p = n, i = n - 1; i >= 1; i--) { + if (d[v][rk[u][i]] > d[v][rk[u][p]]) { + ans = min(ans, d[u][rk[u][i]] + d[v][rk[u][p]] + w); + p = i; + } } + } } ``` diff --git a/docs/graph/mst.md b/docs/graph/mst.md index 5ed0977f..ebe15c7c 100644 --- a/docs/graph/mst.md +++ b/docs/graph/mst.md @@ -20,6 +20,7 @@ Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal ### 实现 伪代码： +