From 1a005ae47b202ba2fa08bf6bbc2d38e24621c509 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Sun, 14 Jul 2019 03:21:13 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/basic/construction.md | 2 +- docs/basic/greedy.md | 2 +- docs/ds/block-array.md | 4 +- docs/ds/divide-combine.md | 2 +- docs/ds/dsu.md | 2 +- docs/ds/queue.md | 4 +- docs/ds/segment-tree-beats.md | 2 +- docs/ds/stl/bitset.md | 2 +- docs/geometry/half-plane-intersection.md | 2 +- docs/geometry/nearest-points.md | 8 +-- docs/graph/dynamic-tree-divide.md | 2 +- docs/math/du-sieves.md | 2 +- docs/math/quick-pow.md | 92 +++++++++++++++----------------- docs/misc/parallel-binsearch.md | 4 +- docs/search/backtracking.md | 8 +-- 15 files changed, 67 insertions(+), 71 deletions(-) diff --git a/docs/basic/construction.md b/docs/basic/construction.md index fbda99f4..19bba71b 100644 --- a/docs/basic/construction.md +++ b/docs/basic/construction.md @@ -94,7 +94,7 @@ $$ #### Problem -[BZOJ4971:\[Lydsy1708 月赛\] 记忆中的背包](https://www.lydsy.com/JudgeOnline/problem.php?id=4971) +[BZOJ4971:\[Lydsy1708 月赛\]记忆中的背包](https://www.lydsy.com/JudgeOnline/problem.php?id=4971) #### Solution diff --git a/docs/basic/greedy.md b/docs/basic/greedy.md index ff85f068..29932c60 100644 --- a/docs/basic/greedy.md +++ b/docs/basic/greedy.md @@ -23,7 +23,7 @@ 用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。 -有些题的排序方法非常显然，如[Luogu P1209 \[USACO1.3\] 修理牛棚 Barn Repair](https://www.luogu.org/problemnew/show/P1209)就是将输入数组差分后排序模拟求值。 +有些题的排序方法非常显然，如[Luogu P1209\[USACO1.3\]修理牛棚 Barn Repair](https://www.luogu.org/problemnew/show/P1209)就是将输入数组差分后排序模拟求值。 然而有些时候很难直接一下子看出排序方法，比如[NOIP 2012 国王游戏](https://vijos.org/p/1779)就很容易凭直觉而错误地以 $a$ 或 $b$ 为关键字排序，过样例之后提交就发现 WA 了 QAQ。一个~~众所周知的~~常见办法就是尝试交换数组相邻的两个元素来 **推导** 出正确的排序方法。我们假设这题输入的俩个数用一个结构体来保存 diff --git a/docs/ds/block-array.md b/docs/ds/block-array.md index f8e66375..78fb525d 100644 --- a/docs/ds/block-array.md +++ b/docs/ds/block-array.md @@ -63,7 +63,7 @@ int Answer(int l, int r, int c) { ### 例题 2：寒夜方舟 两种操作： -1\. 区间 $[x,y]$ 每个数都变成 $z$ 2. 查询区间 $[x,y]$ 内小于等于 $z$ 的数的个数 +1.区间 $[x,y]$ 每个数都变成 $z$ 2. 查询区间 $[x,y]$ 内小于等于 $z$ 的数的个数 用 `dlt` 保存现在块内是否被整体赋值了。用一个值表示没有。对于边角块，查询前要 `pushdown` ，把块内存的信息下放到每一个数上。赋值之后记得从新 `sort` 一遍。其他方面同上题。 @@ -132,5 +132,5 @@ int Answer(int l, int r, int c) { 2. [区间修改，区间查询](https://loj.ac/problem/132) 3. [【模板】线段树 2](https://www.luogu.org/problemnew/show/P3373) 4. [\[Ynoi2019 模拟赛\]Yuno loves sqrt technology III](https://www.luogu.org/problemnew/show/P5048) -5. [\[Violet\] 蒲公英](https://www.luogu.org/problemnew/show/P4168) +5. [\[Violet\]蒲公英](https://www.luogu.org/problemnew/show/P4168) 6. [作诗](https://www.luogu.org/problemnew/show/P4135) diff --git a/docs/ds/divide-combine.md b/docs/ds/divide-combine.md index a1536909..db10121d 100644 --- a/docs/ds/divide-combine.md +++ b/docs/ds/divide-combine.md @@ -22,7 +22,7 @@ 2. $\forall i,P_i\in[1,n]$ . 3. $\nexists i,j\in[1,n],P_i=P_j$ . - **连续段** ：对于排列 $P$ ，定义连续段 $(P,[l,r])$ 表示一个区间 $[l,r]$ ，要求 $P_{l\sim r}$ 值域是连续的。说得更形式化一点，对于排列 $P$ ，连续段表示一个区间 $[l,r]$ 满足： + **连续段** ：对于排列 $P$ ，定义连续段 $(P,[l,r])$ 表示一个区间 $[l,r]$ ，要求 $P_{l\sim r}$ 值域是连续的。说得更形式化一点，对于排列 $P$ ，连续段表示一个区间 $[l,r]$ 满足： $$ (\nexists\ x,z\in[l,r],y\notin[l,r],\ P_x 4. 删除后端的二元组 > 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$ . ### 离线算法 @@ -172,7 +172,7 @@ namespace DQ { // 双栈模拟双端队列 pii fr[M], bc[M]; // front,back; fi:w,se:v; int tf = 0, tb = 0; // top int ff[M][P], fb[M][P]; -void update(pii* s, int f[][P], int i) { // update f[i] from f[i-1] +void update(pii *s, int f[][P], int i) { // update f[i] from f[i-1] FOR(j, 0, p - 1) { f[i][j] = f[i - 1][j]; if (~f[i - 1][_(j - s[i].fi)]) diff --git a/docs/ds/segment-tree-beats.md b/docs/ds/segment-tree-beats.md index 28b985a9..a23c9303 100644 --- a/docs/ds/segment-tree-beats.md +++ b/docs/ds/segment-tree-beats.md @@ -340,7 +340,7 @@ CTSN？赤兔少年。吃土少年。 > 4. 对 B 做区间加 > 5. 询问区间的 $A_i+B_i$ 的最大值 > -> $n,m\le 3\times 10^5$ 。 +> $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 序列的最大值。然后合并信息该怎么合并就怎么合并了。 diff --git a/docs/ds/stl/bitset.md b/docs/ds/stl/bitset.md index 182ef806..8d20013d 100644 --- a/docs/ds/stl/bitset.md +++ b/docs/ds/stl/bitset.md @@ -52,7 +52,7 @@ bitset<1000> bs; // a bitset with 1000 bits ### 运算符 - `operator []` : 访问其特定的一位。 -- `operator ==/!=` : 比较两个 `bitset` 内容是否完全一样。 +- `operator ==/！=` : 比较两个 `bitset` 内容是否完全一样。 - `operator &/&=/|/| =/^/^=/~` : 进行按位与/或/异或/取反操作。 ** `bitset` 只能与 `bitset` 进行位运算** ，若要和整型进行位运算，要先将整型转换为 `bitset` 。 - `operator <>/<<=/>>=` : 进行二进制左移/右移。 - `operator <>` : 流运算符，这意味着你可以通过 `cin/cout` 进行输入输出。 diff --git a/docs/geometry/half-plane-intersection.md b/docs/geometry/half-plane-intersection.md index 2ad1ea91..6ac4fb9d 100644 --- a/docs/geometry/half-plane-intersection.md +++ b/docs/geometry/half-plane-intersection.md @@ -145,4 +145,4 @@ t[r + 1] = its(q[l + 1], q[r]); //再求出新的交点 [POJ 1279 Art Gallery](http://poj.org/problem?id=1279)求多边形的核 -[\[CQOI2006\] 凸多边形](https://www.lydsy.com/JudgeOnline/problem.php?id=2618) +[\[CQOI2006\]凸多边形](https://www.lydsy.com/JudgeOnline/problem.php?id=2618) diff --git a/docs/geometry/nearest-points.md b/docs/geometry/nearest-points.md index 5a8a6b77..e3f0e072 100644 --- a/docs/geometry/nearest-points.md +++ b/docs/geometry/nearest-points.md @@ -133,11 +133,11 @@ rec(0, n - 1); ## 习题 -- [UVA 10245 "The Closest Pair Problem" \[难度：低\]](https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1186) -- [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) +- [UVA 10245 "The Closest Pair Problem"\[难度：低\]](https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1186) +- [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) - [Google CodeJam 2009 Final "Min Perimeter"\[难度：中\]](https://code.google.com/codejam/contest/311101/dashboard#s=a&a=1) -- [SPOJ #7029 CLOSEST "Closest Triple" \[难度：中\]](https://www.spoj.com/problems/CLOSEST/) +- [SPOJ #7029 CLOSEST "Closest Triple"\[难度：中\]](https://www.spoj.com/problems/CLOSEST/) * * * diff --git a/docs/graph/dynamic-tree-divide.md b/docs/graph/dynamic-tree-divide.md index 847f13e6..afc9e681 100644 --- a/docs/graph/dynamic-tree-divide.md +++ b/docs/graph/dynamic-tree-divide.md @@ -69,7 +69,7 @@ int main() { 1. 反转一个结点的颜色（白变黑，黑变白）； 2. 询问树上两个最远的黑点的距离。 - $n\le 10^5,m\le 5\times 10^5$ + $n\le 10^5,m\le 5\times 10^5$ 求出点分树，对于每个结点 $x$ 维护两个 **可删堆** 。 $dist[x]$ 存储结点 $x$ 代表的联通块中的所有黑点到 $x$ 的距离信息， $ch[x]$ 表示结点 $x$ 在点分树上的所有儿子和它自己中的黑点到 $x$ 的距离信息，由于本题贪心的求答案方法，且两个来自于同一子树的路径不能成为一条完成的路径，我们只在这个堆中插入其自己的值和其每个子树中的最大值。我们发现， $ch[x]$ 中最大的两个值（如果没有两个就是所有值）的和就是分治时分支中心为 $x$ 时经过结点 $x$ 的最长黑端点路径。我们可以用可删堆 $ans$ 存储所有结点的答案，这个堆中的最大值就是我们所求的答案。 diff --git a/docs/math/du-sieves.md b/docs/math/du-sieves.md index 159c15f5..f8e48b48 100644 --- a/docs/math/du-sieves.md +++ b/docs/math/du-sieves.md @@ -179,7 +179,7 @@ int main() { ## 问题二 -??? note "[\[LuoguP3768\] 简单的数学题](https://www.luogu.org/problemnew/show/P3768)" +??? note "[\[LuoguP3768\]简单的数学题](https://www.luogu.org/problemnew/show/P3768)" 大意：求 $$ diff --git a/docs/math/quick-pow.md b/docs/math/quick-pow.md index 872a7048..958931a0 100644 --- a/docs/math/quick-pow.md +++ b/docs/math/quick-pow.md @@ -93,56 +93,52 @@ long long qpow(long long a, long long b, long long p) { ??? note "前置技能" 请先学习[高精度](https://oi-wiki.org/math/bignum/) -??? note "例题【NOIP2003普及组改编·麦森数】（[原题在此](https://www.luogu.org/problemnew/show/P1045)）" - 题目大意：从文件中输入P（1000 - using namespace std; - int a[505],b[505],t[505],i,j; - int mult(int x[],int y[])//高精度乘法 - { - memset(t,0,sizeof(t)); - for(i=1;i<=x[0];i++) - { - for(j=1;j<=y[0];j++) - { - if(i+j-1>100) continue; - t[i+j-1]+=x[i]*y[j]; - t[i+j]+=t[i+j-1]/10; - t[i+j-1]%=10; - t[0]=i+j; - } - } - memcpy(b,t,sizeof(b)); - } - void ksm(int p)//快速幂 - { - if(p==1) - { - memcpy(b,a,sizeof(b)); - return; - } - ksm(p/2); - mult(b,b); - if(p%2==1) mult(b,a); - } - int main() - { - int p; - scanf("%d",&p); - a[0]=1;a[1]=2; - b[0]=1;b[1]=1; - ksm(p); - for(i=100;i>=1;i--) - { - if(i==1) - { - printf("%d\n",b[i]-1); - } - else printf("%d",b[i]); - } - } +#include +using namespace std; +int a[505], b[505], t[505], i, j; +int mult(int x[], int y[]) //高精度乘法 +{ + memset(t, 0, sizeof(t)); + for (i = 1; i <= x[0]; i++) { + for (j = 1; j <= y[0]; j++) { + if (i + j - 1 > 100) continue; + t[i + j - 1] += x[i] * y[j]; + t[i + j] += t[i + j - 1] / 10; + t[i + j - 1] %= 10; + t[0] = i + j; + } + } + memcpy(b, t, sizeof(b)); +} +void ksm(int p) //快速幂 +{ + if (p == 1) { + memcpy(b, a, sizeof(b)); + return; + } + ksm(p / 2); + mult(b, b); + if (p % 2 == 1) mult(b, a); +} +int main() { + int p; + scanf("%d", &p); + a[0] = 1; + a[1] = 2; + b[0] = 1; + b[1] = 1; + ksm(p); + for (i = 100; i >= 1; i--) { + if (i == 1) { + printf("%d\n", b[i] - 1); + } else + printf("%d", b[i]); + } +} ``` diff --git a/docs/misc/parallel-binsearch.md b/docs/misc/parallel-binsearch.md index d78e1f23..3d5e4197 100644 --- a/docs/misc/parallel-binsearch.md +++ b/docs/misc/parallel-binsearch.md @@ -30,8 +30,8 @@ ## 详解 注： -1\. 为可读性，文中代码或未采用实际竞赛中的常见写法。 -2\. 若觉得某段代码有难以理解之处，请先参考之前题目的解释， +1.为可读性，文中代码或未采用实际竞赛中的常见写法。 +2.若觉得某段代码有难以理解之处，请先参考之前题目的解释， 因为节省篇幅解释过的内容不再赘述。 从普通二分说起： diff --git a/docs/search/backtracking.md b/docs/search/backtracking.md index 425d9158..70d579c9 100644 --- a/docs/search/backtracking.md +++ b/docs/search/backtracking.md @@ -6,13 +6,13 @@ ## 实现过程 -1\. 构造空间树。 +1.构造空间树。 -2\. 进行遍历。 +2.进行遍历。 -3\. 如遇到边界条件，即不再向下搜索，转而搜索另一条链。 +3.如遇到边界条件，即不再向下搜索，转而搜索另一条链。 -4\. 达到目标条件，输出结果。 +4.达到目标条件，输出结果。 ## 经典例题： -- 2.11.0