From 222da9f4630d5930e97cab9a1992a8d7a4472a4c Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Sat, 31 Oct 2020 09:17:53 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/topic/bracket.md | 57 +++++++++++++++++++++++++++------------------------ 1 file changed, 30 insertions(+), 27 deletions(-) diff --git a/docs/topic/bracket.md b/docs/topic/bracket.md index b742b704..e69749b2 100644 --- a/docs/topic/bracket.md +++ b/docs/topic/bracket.md @@ -8,7 +8,7 @@ author: sshwy 例如 $(())()$ 是合法括号序列，而 $)()$ 不是。 -有时候会有多种不同的括号，如 $[()]\{\}$。这样的变种括号序列与朴素括号序列有相似的定义。 +有时候会有多种不同的括号，如 $[()]\{\}$ 。这样的变种括号序列与朴素括号序列有相似的定义。 本文将会介绍与括号序列相关的经典问题。 @@ -23,63 +23,66 @@ author: sshwy - 如果 $s_i$ 是右括号且栈非空且栈顶元素是 $s_i$ 对应的左括号，就弹出栈顶元素。 - 若不满足上述条件，则将 $s_i$ 圧入栈中。 -在遍历整个 $s$ 后，若栈是空的，那么 $s$ 就是合法括号序列，否则就不是。算法复杂度 $O(n)$。 +在遍历整个 $s$ 后，若栈是空的，那么 $s$ 就是合法括号序列，否则就不是。算法复杂度 $O(n)$ 。 ## 合法括号序列计数 -考虑求出长度为 $2n$ 的合法括号序列 $s$ 的个数 $f_n$。不妨枚举与 $s_1$ 匹配的括号的位置，假设是 $2i+2$。它将整个序列又分成了两个更短的合法括号序列。因此 +考虑求出长度为 $2n$ 的合法括号序列 $s$ 的个数 $f_n$ 。不妨枚举与 $s_1$ 匹配的括号的位置，假设是 $2i+2$ 。它将整个序列又分成了两个更短的合法括号序列。因此 $$ f_n=\sum_{i=0}^{n-1}f_if_{n-i-1} $$ -这同样是卡特兰数的递推式。也就是说 $f_n=\frac{1}{n+1}\binom{2n}{n}$。 +这同样是卡特兰数的递推式。也就是说 $f_n=\frac{1}{n+1}\binom{2n}{n}$ 。 -当然，对于变种合法括号序列的计数，方法是类似的。假设有 $k$ 种不同类型的括号，那么有 $f'_n=\frac{1}{n+1}\binom{2n}{n}k^n$。 +当然，对于变种合法括号序列的计数，方法是类似的。假设有 $k$ 种不同类型的括号，那么有 $f'_n=\frac{1}{n+1}\binom{2n}{n}k^n$ 。 ## 字典序后继 -给出合法的括号序列 $s$，我们要求出（将长度为 $|s|$ 的所有合法括号序列）按字典序从小到大排序后 $s$ 的下一个合法括号序列，我们认为左括号的字典序小于右括号。在本问题中我们不考虑变种括号序列。 +给出合法的括号序列 $s$ ，我们要求出（将长度为 $|s|$ 的所有合法括号序列）按字典序从小到大排序后 $s$ 的下一个合法括号序列，我们认为左括号的字典序小于右括号。在本问题中我们不考虑变种括号序列。 -我们需要找到一个最大的 $i$ 使得 $s_i$ 是左括号然后将其变成右括号，并将 $s[i+1,|s|]$ 这部分重构一下。另外，$i$ 必须满足：$s[1,i-1]$ 中左括号的数量**大于**右括号的数量。 +我们需要找到一个最大的 $i$ 使得 $s_i$ 是左括号然后将其变成右括号，并将 $s[i+1,|s|]$ 这部分重构一下。另外， $i$ 必须满足： $s[1,i-1]$ 中左括号的数量 **大于** 右括号的数量。 -不妨设当 $s_i$ 变成右括号后，$s[1,i]$ 中左括号比右括号多了 $k$ 个。那么我们就让 $s$ 的最后 $k$ 个字符变成右括号，而 $s[i+1,|s|-k]$ 则用 $((\dots(())\dots))$ 的形式填充即可，因为这样填充的字典序最小。 +不妨设当 $s_i$ 变成右括号后， $s[1,i]$ 中左括号比右括号多了 $k$ 个。那么我们就让 $s$ 的最后 $k$ 个字符变成右括号，而 $s[i+1,|s|-k]$ 则用 $((\dots(())\dots))$ 的形式填充即可，因为这样填充的字典序最小。 -该算法的时间复杂度是 $O(n)$。 +该算法的时间复杂度是 $O(n)$ 。 ??? note "参考实现" ```cpp - bool next_balanced_sequence(string & s) { - int n = s.size(); - int depth = 0; - for (int i = n - 1; i >= 0; i--) { - if (s[i] == '(') depth--; - else depth++; + bool next_balanced_sequence(string& s) { + int n = s.size(); + int depth = 0; + for (int i = n - 1; i >= 0; i--) { + if (s[i] == '(') + depth--; + else + depth++; - if (s[i] == '(' && depth > 0) { - depth--; - int open = (n - i - 1 - depth) / 2; - int close = n - i - 1 - open; - string next = s.substr(0, i) + ')' + string(open, '(') + string(close, ')'); - s.swap(next); - return true; - } + if (s[i] == '(' && depth > 0) { + depth--; + int open = (n - i - 1 - depth) / 2; + int close = n - i - 1 - open; + string next = + s.substr(0, i) + ')' + string(open, '(') + string(close, ')'); + s.swap(next); + return true; } - return false; + } + return false; } ``` ## 字典序计算 -给出合法的括号序列 $s$，我们要求出它的字典序排名。 +给出合法的括号序列 $s$ ，我们要求出它的字典序排名。 考虑求出字典序比 $s$ 小的括号序列 $p$ 的个数。 -不妨设 $p_i