From cc7b7f60f7deff272ebc6ae175a535eef22ceac0 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Sun, 4 Aug 2019 08:15:29 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/dp/opt/monotonous-queue-stack.md | 4 ++-- docs/ds/seg-beats.md | 26 +++++++++++++------------- docs/ds/top-tree.md | 1 + docs/graph/topo.md | 2 +- docs/intro/editor/devcpp.md | 1 + docs/intro/editor/vscode.md | 3 +-- docs/lang/basic.md | 1 + docs/math/inverse.md | 2 +- docs/math/min-25.md | 2 +- 9 files changed, 22 insertions(+), 20 deletions(-) diff --git a/docs/dp/opt/monotonous-queue-stack.md b/docs/dp/opt/monotonous-queue-stack.md index 95fde653..9d8d6385 100644 --- a/docs/dp/opt/monotonous-queue-stack.md +++ b/docs/dp/opt/monotonous-queue-stack.md @@ -6,8 +6,8 @@ author: TrisolarisHD, hsfzLZH1, Ir1d, greyqz, Anguei, billchenchina, Chrogeek, C ??? note " 例题[CF372C Watching Fireworks is Fun](http://codeforces.com/problemset/problem/372/C)" 题目大意：城镇中有 $n$ 个位置，有 $m$ 个烟花要放。第 $i$ 个烟花放出的时间记为 $t_i$ ，放出的位置记为 $a_i$ 。如果烟花放出的时候，你处在位置 $x$ ，那么你将收获 $b_i-|a_i-x|$ 点快乐值。 - - 初始你可在任意位置，你每个单位时间可以移动不大于 $d$ 个单位距离。现在你需要最大化你能获得的快乐值。 + + 初始你可在任意位置，你每个单位时间可以移动不大于 $d$ 个单位距离。现在你需要最大化你能获得的快乐值。 设 $f_{i,j}$ 表示在放第 $i$ 个烟花时，你的位置在 $j$ 所能获得的最大快乐值。 diff --git a/docs/ds/seg-beats.md b/docs/ds/seg-beats.md index 1f4cbea9..6f329018 100644 --- a/docs/ds/seg-beats.md +++ b/docs/ds/seg-beats.md @@ -6,7 +6,7 @@ ### HDU5306 Gorgeous Sequence -> 维护一个序列 $a$： +> 维护一个序列 $a$ ： > > 1. `0 l r t` $\forall l\le i\le r,\ a_i=\min(a_i,t)$ 。 > 2. `1 l r` 输出区间 $[l,r]$ 中的最大值。 @@ -14,7 +14,7 @@ > > 多组数据， $T\le 100,n\le 10^6,\sum m\le 10^6$ 。 -区间取 min，意味着只对那些大于 $t$ 的数有更改。因此这个操作的对象不再是整个区间，而是“这个区间中大于 $t$ 的数”。于是我们可以有这样的思路：每个结点维护该区间的最大值 $Max$、次大值 $Se$、区间和 $Sum$ 以及最大值的个数 $Cnt$。接下来我们考虑区间对 $t$ 取 $\min$ 的操作。 +区间取 min，意味着只对那些大于 $t$ 的数有更改。因此这个操作的对象不再是整个区间，而是“这个区间中大于 $t$ 的数”。于是我们可以有这样的思路：每个结点维护该区间的最大值 $Max$ 、次大值 $Se$ 、区间和 $Sum$ 以及最大值的个数 $Cnt$ 。接下来我们考虑区间对 $t$ 取 $\min$ 的操作。 1. 如果 $Max\le t$ ，显然这个 $t$ 是没有意义的，直接返回； 2. 如果 $Se 长度为 $n$ 的序列，支持区间加 $x$/区间对 $x$ 取 $\max$ /区间对 $x$ 取 $\min$ /求区间和/求区间最大值/求区间最小值。 +> 长度为 $n$ 的序列，支持区间加 $x$ /区间对 $x$ 取 $\max$ /区间对 $x$ 取 $\min$ /求区间和/求区间最大值/求区间最小值。 > > $N,M\le 5\times 10^5,|A_i|\le 10^8$ 。 @@ -142,7 +142,7 @@ signed main() { 1. 我们认为区间加的标记是最优先的，其余两种标记地位平等。 2. 对一个结点加上一个 $v$ 标记，除了用 $v$ 更新卫星信息和当前结点的区间加标记外，我们用这个 v 更新区间 $\max$ 和区间 $\min$ 的标记。 -3. 对一个结点取 $v$ 的 $\min$ （这里忽略暴搜的过程，假定标记满足添加的条件），除了更新卫星信息，我们要与区间 $\max$ 的标记做比较。如果 $v$ 小于区间 $\max$ 的标记，则所有的数最后都会变成 v，那么把区间 $\max$ 的标记也变成 $v$。否则不管。 +3. 对一个结点取 $v$ 的 $\min$ （这里忽略暴搜的过程，假定标记满足添加的条件），除了更新卫星信息，我们要与区间 $\max$ 的标记做比较。如果 $v$ 小于区间 $\max$ 的标记，则所有的数最后都会变成 v，那么把区间 $\max$ 的标记也变成 $v$ 。否则不管。 4. 区间取 v 的 $\max$ 同理。 另外，BZOJ 这道题卡常……多数组线段树的常数比结构体线段树的常数大……在维护信息的时侯，当只有一两个数的时侯可能发生数集重合，比如一个数既是最大值又是次小值。这种要特判。 @@ -320,14 +320,14 @@ int main() { ### Mzl loves segment tree -> 两个序列 $A,B$，一开始 $B$ 中的数都是 $0$。维护的操作是： +> 两个序列 $A,B$ ，一开始 $B$ 中的数都是 $0$ 。维护的操作是： > > 1. 对 $A$ 做区间取 $\min$ > 2. 对 $A$ 做区间取 $\max$ > 3. 对 $A$ 做区间加 > 4. 询问 $B$ 的区间和 > -> 每次操作完后，如果 $A_i$ 的值发生变化，就给 $B_i$ 加 $1$。 $n,m\le 3\times 10^5$ 。 +> 每次操作完后，如果 $A_i$ 的值发生变化，就给 $B_i$ 加 $1$ 。 $n,m\le 3\times 10^5$ 。 先考虑最容易的区间加操作。只要 $x\neq 0$ 那么整个区间的数都变化，所以给 B 作一次区间加即可。 @@ -335,7 +335,7 @@ int main() { ### CTSN loves segment tree -> 两个序列 $A,B$： +> 两个序列 $A,B$ ： > > 1. 对 $A$ 做区间取 $\min$ > 2. 对 $B$ 做区间取 $\min$ @@ -345,7 +345,7 @@ int main() { > > $n,m\le 3\times 10^5$ 。 -我们把区间中的 **位置** 分成四类：在 $A,B$ 中同是区间最大值的位置、在 $A$ 中是区间最大值在 $B$ 中不是的位置、在 $B$ 中是区间最大值在 $A$ 中不是的位置、在 $A,B$ 中都不是区间最大值的位置。对这四类数分别维护 **答案** 和 **标记** 即可。举个例子，我们维护 $C_{1\sim 4},M_{1\sim 4},A_{max},B_{max}$ 分别表示当前区间中四类数的个数，四类数的答案的最大值，$A$ 序列的最大值、$B$ 序列的最大值。然后合并信息该怎么合并就怎么合并了。 +我们把区间中的 **位置** 分成四类：在 $A,B$ 中同是区间最大值的位置、在 $A$ 中是区间最大值在 $B$ 中不是的位置、在 $B$ 中是区间最大值在 $A$ 中不是的位置、在 $A,B$ 中都不是区间最大值的位置。对这四类数分别维护 **答案** 和 **标记** 即可。举个例子，我们维护 $C_{1\sim 4},M_{1\sim 4},A_{max},B_{max}$ 分别表示当前区间中四类数的个数，四类数的答案的最大值， $A$ 序列的最大值、 $B$ 序列的最大值。然后合并信息该怎么合并就怎么合并了。 复杂度仍是 $O(m\log_2^2 n)$ 。 @@ -361,7 +361,7 @@ int main() { #### 历史最大值 -简单地说，一个位置的历史最大值就是当前位置下曾经出现过的数的最大值。形式化地定义，我们定义一个辅助数组 $B$，一开始与 $A$ 完全相同。在 $A$ 的每次操作后，我们对整个数组取 $\max$： +简单地说，一个位置的历史最大值就是当前位置下曾经出现过的数的最大值。形式化地定义，我们定义一个辅助数组 $B$ ，一开始与 $A$ 完全相同。在 $A$ 的每次操作后，我们对整个数组取 $\max$ ： $$ \forall i\in[1,n],\ B_i=\max(B_i,A_i) @@ -375,7 +375,7 @@ $$ #### 历史版本和 -辅助数组 $B$ 一开始全部是 $0$。在每一次操作后，我们把整个 $A$ 数组累加到 $B$ 数组上 +辅助数组 $B$ 一开始全部是 $0$ 。在每一次操作后，我们把整个 $A$ 数组累加到 $B$ 数组上 $$ \forall i\in[1,n], \ B_i=B_i+A_i @@ -398,19 +398,19 @@ $$ > > 每次操作后，我们都进行一次更新， $\forall i\in [1,n],\ B_i=\max(B_i,A_i)$ 。 $n,m\le 10^5$ 。 -我们先不考虑操作 1。那么只有区间加的操作，我们维护标记 $Add$ 表示当前区间增加的值，这个标记可以解决区间 $\max$ 的问题。接下来考虑历史区间 $\max$。我们定义标记 $Pre$，该标记的含义是：在该标记的生存周期内，$Add$ 标记的历史最大值。 +我们先不考虑操作 1。那么只有区间加的操作，我们维护标记 $Add$ 表示当前区间增加的值，这个标记可以解决区间 $\max$ 的问题。接下来考虑历史区间 $\max$ 。我们定义标记 $Pre$ ，该标记的含义是：在该标记的生存周期内， $Add$ 标记的历史最大值。 这个定义可能比较模糊。因此我们先解释一下标记的生存周期。一个标记会经历这样的过程： 1. 在结点 $u$ 被建立。 2. 在结点 $u$ 接受若干个新的标记的同时，与新的标记合并（指同类标记） -3. 结点 $u$ 的标记下传给 $u$ 的儿子，$u$ 的标记清空 +3. 结点 $u$ 的标记下传给 $u$ 的儿子， $u$ 的标记清空 我们认为在这个过程中，从 1 开始到 3 之前，都是结点 $u$ 的标记的生存周期。两个标记合并后，成为同一个标记，那么他们的生存周期也会合并（即取建立时间较早的那个做为生存周期的开始）。一个与之等价的说法是，从上次把这个结点的标记下传的时刻到当前时刻这一时间段。 为什么要定义生存周期？利用这个概念，我们可以证明：在一个结点标记的生存周期内，其子结点均不会发生任何变化，并保留在这个生存周期之前的状态。道理很简单，因为在这个期间你是没有下传标记的。 -于是，你就可以保证，在当前标记生存周期内的历史 $Add$ 的最大值是可以更新到子结点的标记和信息上的。因为子结点的标记和信息在这个时间段内都没有变过。于是我们把 $u$ 的标记下传给它的儿子 $s$，不难发现 +于是，你就可以保证，在当前标记生存周期内的历史 $Add$ 的最大值是可以更新到子结点的标记和信息上的。因为子结点的标记和信息在这个时间段内都没有变过。于是我们把 $u$ 的标记下传给它的儿子 $s$ ，不难发现 $$ Pre_s=\max(Pre_s,Pre_u+Add_s),Add_s=Add_u+Add_s diff --git a/docs/ds/top-tree.md b/docs/ds/top-tree.md index e69de29b..8b137891 100644 --- a/docs/ds/top-tree.md +++ b/docs/ds/top-tree.md @@ -0,0 +1 @@ + diff --git a/docs/graph/topo.md b/docs/graph/topo.md index 356cd539..c760961c 100644 --- a/docs/graph/topo.md +++ b/docs/graph/topo.md @@ -8,7 +8,7 @@ 但是如果某一天排课的老师打瞌睡了，说想要学习 算法导论，还得先学 机器学习，而 机器学习 的前置课程又是 算法导论，然后你就一万脸懵逼了，我到底应该先学哪一个？当然我们在这里不考虑什么同时学几个课程的情况。在这里，算法导论 和 机器学习 间就出现了一个环，显然你现在没办法弄清楚你需要学什么了，于是你也没办法进行拓扑排序了。因而如果有向图中存在环路，那么我们就没办法进行 拓扑排序 了。 -因此我们可以说 在一个 [DAG（有向无环图）](/graph/dag)中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 $u$ 到 $v$ 的有向边 $(u,v)$ , 都可以有 $u$ 在 $v$ 的前面。 +因此我们可以说 在一个[DAG（有向无环图）](/graph/dag)中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 $u$ 到 $v$ 的有向边 $(u,v)$ , 都可以有 $u$ 在 $v$ 的前面。 还有给定一个 DAG，如果从 $i$ 到 $j$ 有边，则认为 $j$ 依赖于 $i$ 。如果 $i$ 到 $j$ 有路径（ $i$ 可达 $j$ ），则称 $j$ 间接依赖于 $i$ 。 diff --git a/docs/intro/editor/devcpp.md b/docs/intro/editor/devcpp.md index e69de29b..8b137891 100644 --- a/docs/intro/editor/devcpp.md +++ b/docs/intro/editor/devcpp.md @@ -0,0 +1 @@ + diff --git a/docs/intro/editor/vscode.md b/docs/intro/editor/vscode.md index afbb6e6b..d0bf34fe 100644 --- a/docs/intro/editor/vscode.md +++ b/docs/intro/editor/vscode.md @@ -11,8 +11,7 @@ Visual Studio Code（以下简称 VS Code) 是一个免费、开源、跨平台 #### 安装语言插件 首先我们要在 VS Code 中安装你要使用的语言的插件。直接打开插件商店，然后在搜索栏中输入 `@category:"programming languages"` ，然后找到对应的插件，安装，OK！ -` -![](./images/editor-vscode2.png) +\`![](./images/editor-vscode2.png) #### 使用 CodeRunner 插件 diff --git a/docs/lang/basic.md b/docs/lang/basic.md index e69de29b..8b137891 100644 --- a/docs/lang/basic.md +++ b/docs/lang/basic.md @@ -0,0 +1 @@ + diff --git a/docs/math/inverse.md b/docs/math/inverse.md index c14121ac..1180f913 100644 --- a/docs/math/inverse.md +++ b/docs/math/inverse.md @@ -85,7 +85,7 @@ for (int i = 2; i <= n; ++i) inv[i] = (long long)(p - p / i) * inv[p % i] % p; 另外，根据线性求逆元方法的式子： $i^{-1} \equiv -kj^{-1} \pmod p$ -递归求解 $j^-1$ , 直到 $j=1$ 返回 $1$。 +递归求解 $j^-1$ , 直到 $j=1$ 返回 $1$ 。 中间优化可以加入一个记忆化来避免多次递归导致的重复，这样求 $1,2,...,n$ 中所有数的逆元的时间复杂度仍是 $O(n)$ 。 diff --git a/docs/math/min-25.md b/docs/math/min-25.md index 638ffb1e..77a5f1fa 100644 --- a/docs/math/min-25.md +++ b/docs/math/min-25.md @@ -1,6 +1,6 @@ author: TrisolarisHD, Xeonacid -由于其由 [Min_25](http://min-25.hatenablog.com/) 发明并最早开始使用，故称「Min_25 筛」。 +由于其由[Min_25](http://min-25.hatenablog.com/)发明并最早开始使用，故称「Min_25 筛」。 > 从此种筛法的思想方法来说，其又被称为「Extended Eratosthenes Sieve」。 -- 2.11.0