OI-wiki 括号序列专题合法性判定、卡特兰计数与字典序算法的完整解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读括号序列balanced bracket sequence是 OI / ICPC 竞赛中最基础也最高频的字符串结构之一从栈模拟判合法到卡特兰数计数再到字典序后继与排名求解几乎覆盖了该主题的全部经典考点。本文以 OI-wiki docs/topic/bracket.md 为主线结合仓库内 卡特兰数专题 与 普通生成函数 的内容进行纵深扩充读完你将掌握括号序列四大经典问题的算法原理、复杂度分析与可复用的 C 实现。1. 合法括号序列的定义OI-wiki 中对合法括号序列balanced bracket sequence给出了一个递归定义一个仅由(和)构成的字符串 $s$ 是合法的当且仅当它满足以下三条规则之一空串$\varepsilon$ 是合法括号序列包裹如果 $s$ 是合法括号序列那么 $(s)$ 也是合法括号序列拼接如果 $s,t$ 都是合法括号序列那么 $st$ 也是合法括号序列。例如(())()是合法括号序列而)()不是前缀)处左括号数已经少于右括号数且最终左、右括号数不相等。等价刻画从另一个角度看合法括号序列等价于左括号总数等于右括号总数且任意前缀中左括号数不少于右括号数。这一刻画在实际判定与计数中更为常用后文的贪心栈算法正是建立在这个性质之上。变种括号序列实际题目中常出现多种不同的括号如[()]{}。这类变种序列的定义与朴素括号序列相似只是配对关系变为()、[]、{}三组。变种序列要求每一对括号的类型严格匹配即栈顶弹出的必须是当前右括号对应的那一种左括号。OI-wiki 原文还特别注明英语中一般称左括号为 opening bracket右括号为 closing bracket在阅读英文题面与算法资料时常用到这对术语。2. 判断括号序列是否合法贪心 栈判断 $s$ 是否为合法括号序列的经典方法是贪心思想时间复杂度 $O(n)$且同样适用于变种括号序列。2.1 算法流程维护一个栈从左到右依次扫描 $i1,2,\ldots,|s|$如果 $s_i$ 是右括号且栈非空、栈顶元素是 $s_i$ 对应的左括号就弹出栈顶元素否则将 $s_i$ 压入栈中。扫描结束后若栈为空则 $s$ 是合法括号序列否则不是。2.2 正确性论证贪心策略的正确性可以从两方面论证右括号必须立刻匹配最近的左括号当扫描到右括号 $s_i$ 时它只能与尚未匹配的、最靠近它的左括号配对。若栈顶不是与之匹配的左括号则说明二者之间存在未匹配的左括号或类型不匹配此时无论后续字符如何这个右括号都无法找到正确配对因此必然不合法结束时栈空蕴含括号数相等栈中剩余的只能是未匹配的左括号或多余的右括号只要栈非空就说明左右括号没有两两配对序列必然不合法。以)()为例第一个字符)是右括号但栈为空直接压栈结束后栈非空判定为不合法与定义一致。3. 合法括号序列计数卡特兰数3.1 递推式的导出设长度为 $2n$ 的合法括号序列个数为 $f_n$。不妨枚举与 $s_1$ 匹配的那个右括号的位置假设它是第 $2i2$ 个字符编号从 $0$ 开始。那么$s[2..2i1]$夹在 $s_1$ 与它匹配的右括号之间本身是一个长度为 $2i$ 的合法括号序列$s[2i3..2n]$ 是一个长度为 $2(n-i-1)$ 的合法括号序列。由乘法原理并对 $i$ 求和得到$$ f_n\sum_{i0}^{n-1}f_i f_{n-i-1} $$这正是卡特兰数Catalan 数的递推式因此$$ f_n \frac{1}{n1}\binom{2n}{n} $$卡特兰数数列的前几项为 $1,1,2,5,14,42,132,429,1430,\ldots$见 docs/math/combinatorics/catalan.md 中引用的 OEIS A000108。3.2 变种括号序列的计数对于变种括号序列方法是类似的。假设有 $k$ 种不同类型的括号每个左括号位置有 $k$ 种选择与之配对的右括号类型随之确定因此长度为 $2n$ 的变种合法括号序列数为$$ f_n\frac{1}{n1}\binom{2n}{n}k^n $$3.3 与更多组合问题的联系卡特兰数远不止括号计数一个应用。OI-wiki 的 卡特兰数专题 指出其递推关系 $C_n\sum_{i0}^{n-1}C_iC_{n-1-i}$ 具有天然的递归分拆结构并给出了多个等价的组合问题均可通过构造双射互相转化路径计数$n\times n$ 方格图中不越过对角线 $yx$ 的单调路径数为 $C_n$圆内不相交弦$2n$ 个点两两连边且互不相交的方案数为 $C_n$凸多边形三角剖分$(n2)$ 边形对角线不相交地剖分为三角形的方案数为 $C_n$二叉树计数$n$ 个结点的形态不同二叉树数为 $C_n$出栈序列计数进栈序列 $1,2,\ldots,n$ 的合法出栈序列数为 $C_n$±1 数列计数由 $n$ 个 $1$ 和 $n$ 个 $-1$ 组成、任意前缀和非负的数列数为 $C_n$。其中括号序列与格路之间存在直接双射将左括号视为向上一步、右括号视为向右一步合法括号序列恰好对应不越过对角线的合法路径。该专题还通过生成函数见 docs/math/poly/ogf.md 的卡特兰数的生成函数一节证明了通项公式 $C_n\frac{(2n)!}{n!(n1)!}$ 以及递推形式 $C_n\frac{4n-2}{n1}C_{n-1}$这些形式分别将计数问题转化为组合数计算或顺次递推可高效求解。4. 字典序后继求下一个合法括号序列4.1 问题定义给出合法括号序列 $s$要求在按字典序升序排序的长度为 $|s|$ 的所有合法括号序列中求出 $s$ 的下一个合法括号序列。在本问题中约定左括号的字典序小于右括号即()且不考虑变种括号序列。4.2 核心算法OI-wiki 给出的构造思路如下找到最大的下标 $i$使得 $s_i$ 是左括号(并且满足 $s[1,i-1]$ 中左括号的数量大于右括号的数量将 $s_i$ 改为右括号)重构后缀 $s[i1,|s|]$。第二步的合法性由于 $s[1,i-1]$ 中左括号数大于右括号数把 $s_i$ 从(改成)后$s[1,i]$ 仍然是一个前缀合法的序列任意前缀左括号数不少于右括号数这样才有可能扩展成合法序列。第三步的填充策略设 $s_i$ 变成右括号后$s[1,i]$ 中左括号比右括号多 $k$ 个。为了保持总括号数相等序列的最后 $k$ 个字符必须是右括号而中间的 $s[i1,|s|-k]$ 则用$$ ((\dots(())\dots)) $$的形式填充即先连续放尽可能多的左括号再放对应数量的右括号因为这样的填充方式在字典序上最小。该算法的时间复杂度是 $O(n)$。4.3 参考实现OI-wiki 原文代码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; } } return false; }对实现逐行拆解从后往前扫描i n-1递减用一个depth变量记录当前后缀中右括号比左括号多多少个。具体地遇到(时depth--遇到)时depth当遇到s[i](且depth 0时说明把s[i]翻转为)后s[1,i]中左括号仍比右括号多——这正是上文要求的$s[1,i-1]$ 中左括号数量大于右括号数量的等价条件depth 0表示后缀里右括号更多即前缀里左括号更多翻转后前缀盈余的左括号数为depth - 1于是后缀中需要open (n - i - 1 - depth) / 2个左括号和close n - i - 1 - open个右括号前者全部前置、后者全部后置保证字典序最小构造新串next s.substr(0,i) ) string(open,() string(close,))并交换若整个序列已经是字典序最大的合法括号序列形如(((...)))函数返回false表示不存在后继。以 $n3$ 的合法序列字典序枚举为例((())) (()()) (())() ()(()) ()()()从(())()出发扫描到下标 $i2$ 处的(时其后缀中右括号数更多满足条件将其翻转为)得到前缀())此时盈余 $k1$因此最后 1 个字符放)中间用(()填充得到()(())恰好是字典序中的下一个。5. 字典序计算求排名与反推序列5.1 问题定义给出合法括号序列 $s$要求出它在按字典序升序排列的长度为 $|s|$ 的所有合法括号序列中的排名。OI-wiki 给出的方法不是直接数出比 $s$ 大的序列而是数出所有字典序比 $s$ 小的括号序列 $p$ 的个数排名即等于这个数目加 $1$。5.2 转化为 DP 统计设 $p_i s_i$ 且 $\forall, 1\le ji,\ p_js_j$。由于左括号字典序最小$p_i$ 必为左括号而 $s_i$ 必为右括号。于是枚举 $i$满足 $s_i$ 为右括号假设 $p[1,i]$ 中左括号比右括号多 $k$ 个问题转化为统计长度为 $|s|-i$、存在 $k$ 个未匹配的右括号、且不存在未匹配的左括号的括号序列的个数。为此定义 DP 状态$f(i,j)$ 表示长度为 $i$、存在 $j$ 个未匹配的右括号、且不存在未匹配的左括号的括号序列的个数。5.3 转移方程枚举括号序列的第一个字符是什么第一个字符是右括号未匹配的右括号数从 $j-1$ 增加到 $j$即来自 $f(i-1,j-1)$第一个字符是左括号会与一个右括号抵消未匹配的右括号数从 $j1$ 减少到 $j$即来自 $f(i-1,j1)$。因此转移为$$ f(i,j)f(i-1,j-1)f(i-1,j1) $$初始条件 $f(0,0)1$其余 $f(0,j)0\ (j0)$。这个三角形数表实际对应 OEIS 中的 A053121 序列即所谓卡特兰三角形。利用该数组可以在 $O(|s|^2)$ 时间内完成字典序计算$|s|$ 是序列长度DP 表规模为 $O(|s|^2)$。5.4 变种括号序列的推广对于变种括号序列方法是类似的唯一的区别在于需要对每个 $s_i$ 枚举所有比它小的字符并分别累加。在原算法中由于朴素情况下不存在比左括号更小的字符所以只考虑了 $s_i$ 为右括号的情形而在变种场景下例如字符集存在、[、(等多级优先级时每个位置都可能有多于一个更小但可配对的选择需要对它们逐一用 $f$ 数组统计。5.5 由排名反推序列利用同一张 $f$ 数组我们也可以完成反向操作求字典序排名为 $k$ 的合法括号序列。做法是逐位确定字符——在当前位尝试放(若以(为前缀的合法序列总数可预先用 $f$ 数组算得不少于剩余需要跳过的排名 $k$则确定放(否则减去该数量、改放)如此循环直至填满整个序列。这本质上是数位 DP 逐位构造的标准技巧与上述统计过程互为逆运算。6. 小结与复杂度一览问题核心思想时间复杂度判定合法性贪心 栈扫描$O(n)$合法序列计数卡特兰数递推 / 通项公式$O(n)$ 或 $O(n\log n)$组合数字典序后继反向扫描找翻转点 最小字典序重构$O(n)$字典序排名DP 表 $f(i,j)$ 逐位统计$O(s^2)$由排名反推序列利用 $f$ 数组逐位构造$O(s^2)$本文涉及的算法均可在仓库中对应文档继续深挖括号序列计数的完整推导与多组合问题双射见 docs/math/combinatorics/catalan.md生成函数解法见 docs/math/poly/ogf.md卡特兰数的生成函数一节。此外括号序列思想在 OI-wiki 其他专题中也有广泛应用例如 伸展树维护括号序、动态树括号序维护 以及 DFS 序与括号序的结合可作为进一步学习的延伸方向。页首声明本页面核心内容主要译自博文 Balanced bracket sequences俄文原文与英文翻译版其中俄文版版权协议为 Public Domain Leave a Link英文版版权协议为 CC-BY-SA 4.0OI-wiki 在此基础上按自身排版与示例风格进行了整理与扩充。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 括号序列专题：合法性判定、卡特兰计数与字典序算法的完整解析
OI-wiki 括号序列专题合法性判定、卡特兰计数与字典序算法的完整解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读括号序列balanced bracket sequence是 OI / ICPC 竞赛中最基础也最高频的字符串结构之一从栈模拟判合法到卡特兰数计数再到字典序后继与排名求解几乎覆盖了该主题的全部经典考点。本文以 OI-wiki docs/topic/bracket.md 为主线结合仓库内 卡特兰数专题 与 普通生成函数 的内容进行纵深扩充读完你将掌握括号序列四大经典问题的算法原理、复杂度分析与可复用的 C 实现。1. 合法括号序列的定义OI-wiki 中对合法括号序列balanced bracket sequence给出了一个递归定义一个仅由(和)构成的字符串 $s$ 是合法的当且仅当它满足以下三条规则之一空串$\varepsilon$ 是合法括号序列包裹如果 $s$ 是合法括号序列那么 $(s)$ 也是合法括号序列拼接如果 $s,t$ 都是合法括号序列那么 $st$ 也是合法括号序列。例如(())()是合法括号序列而)()不是前缀)处左括号数已经少于右括号数且最终左、右括号数不相等。等价刻画从另一个角度看合法括号序列等价于左括号总数等于右括号总数且任意前缀中左括号数不少于右括号数。这一刻画在实际判定与计数中更为常用后文的贪心栈算法正是建立在这个性质之上。变种括号序列实际题目中常出现多种不同的括号如[()]{}。这类变种序列的定义与朴素括号序列相似只是配对关系变为()、[]、{}三组。变种序列要求每一对括号的类型严格匹配即栈顶弹出的必须是当前右括号对应的那一种左括号。OI-wiki 原文还特别注明英语中一般称左括号为 opening bracket右括号为 closing bracket在阅读英文题面与算法资料时常用到这对术语。2. 判断括号序列是否合法贪心 栈判断 $s$ 是否为合法括号序列的经典方法是贪心思想时间复杂度 $O(n)$且同样适用于变种括号序列。2.1 算法流程维护一个栈从左到右依次扫描 $i1,2,\ldots,|s|$如果 $s_i$ 是右括号且栈非空、栈顶元素是 $s_i$ 对应的左括号就弹出栈顶元素否则将 $s_i$ 压入栈中。扫描结束后若栈为空则 $s$ 是合法括号序列否则不是。2.2 正确性论证贪心策略的正确性可以从两方面论证右括号必须立刻匹配最近的左括号当扫描到右括号 $s_i$ 时它只能与尚未匹配的、最靠近它的左括号配对。若栈顶不是与之匹配的左括号则说明二者之间存在未匹配的左括号或类型不匹配此时无论后续字符如何这个右括号都无法找到正确配对因此必然不合法结束时栈空蕴含括号数相等栈中剩余的只能是未匹配的左括号或多余的右括号只要栈非空就说明左右括号没有两两配对序列必然不合法。以)()为例第一个字符)是右括号但栈为空直接压栈结束后栈非空判定为不合法与定义一致。3. 合法括号序列计数卡特兰数3.1 递推式的导出设长度为 $2n$ 的合法括号序列个数为 $f_n$。不妨枚举与 $s_1$ 匹配的那个右括号的位置假设它是第 $2i2$ 个字符编号从 $0$ 开始。那么$s[2..2i1]$夹在 $s_1$ 与它匹配的右括号之间本身是一个长度为 $2i$ 的合法括号序列$s[2i3..2n]$ 是一个长度为 $2(n-i-1)$ 的合法括号序列。由乘法原理并对 $i$ 求和得到$$ f_n\sum_{i0}^{n-1}f_i f_{n-i-1} $$这正是卡特兰数Catalan 数的递推式因此$$ f_n \frac{1}{n1}\binom{2n}{n} $$卡特兰数数列的前几项为 $1,1,2,5,14,42,132,429,1430,\ldots$见 docs/math/combinatorics/catalan.md 中引用的 OEIS A000108。3.2 变种括号序列的计数对于变种括号序列方法是类似的。假设有 $k$ 种不同类型的括号每个左括号位置有 $k$ 种选择与之配对的右括号类型随之确定因此长度为 $2n$ 的变种合法括号序列数为$$ f_n\frac{1}{n1}\binom{2n}{n}k^n $$3.3 与更多组合问题的联系卡特兰数远不止括号计数一个应用。OI-wiki 的 卡特兰数专题 指出其递推关系 $C_n\sum_{i0}^{n-1}C_iC_{n-1-i}$ 具有天然的递归分拆结构并给出了多个等价的组合问题均可通过构造双射互相转化路径计数$n\times n$ 方格图中不越过对角线 $yx$ 的单调路径数为 $C_n$圆内不相交弦$2n$ 个点两两连边且互不相交的方案数为 $C_n$凸多边形三角剖分$(n2)$ 边形对角线不相交地剖分为三角形的方案数为 $C_n$二叉树计数$n$ 个结点的形态不同二叉树数为 $C_n$出栈序列计数进栈序列 $1,2,\ldots,n$ 的合法出栈序列数为 $C_n$±1 数列计数由 $n$ 个 $1$ 和 $n$ 个 $-1$ 组成、任意前缀和非负的数列数为 $C_n$。其中括号序列与格路之间存在直接双射将左括号视为向上一步、右括号视为向右一步合法括号序列恰好对应不越过对角线的合法路径。该专题还通过生成函数见 docs/math/poly/ogf.md 的卡特兰数的生成函数一节证明了通项公式 $C_n\frac{(2n)!}{n!(n1)!}$ 以及递推形式 $C_n\frac{4n-2}{n1}C_{n-1}$这些形式分别将计数问题转化为组合数计算或顺次递推可高效求解。4. 字典序后继求下一个合法括号序列4.1 问题定义给出合法括号序列 $s$要求在按字典序升序排序的长度为 $|s|$ 的所有合法括号序列中求出 $s$ 的下一个合法括号序列。在本问题中约定左括号的字典序小于右括号即()且不考虑变种括号序列。4.2 核心算法OI-wiki 给出的构造思路如下找到最大的下标 $i$使得 $s_i$ 是左括号(并且满足 $s[1,i-1]$ 中左括号的数量大于右括号的数量将 $s_i$ 改为右括号)重构后缀 $s[i1,|s|]$。第二步的合法性由于 $s[1,i-1]$ 中左括号数大于右括号数把 $s_i$ 从(改成)后$s[1,i]$ 仍然是一个前缀合法的序列任意前缀左括号数不少于右括号数这样才有可能扩展成合法序列。第三步的填充策略设 $s_i$ 变成右括号后$s[1,i]$ 中左括号比右括号多 $k$ 个。为了保持总括号数相等序列的最后 $k$ 个字符必须是右括号而中间的 $s[i1,|s|-k]$ 则用$$ ((\dots(())\dots)) $$的形式填充即先连续放尽可能多的左括号再放对应数量的右括号因为这样的填充方式在字典序上最小。该算法的时间复杂度是 $O(n)$。4.3 参考实现OI-wiki 原文代码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; } } return false; }对实现逐行拆解从后往前扫描i n-1递减用一个depth变量记录当前后缀中右括号比左括号多多少个。具体地遇到(时depth--遇到)时depth当遇到s[i](且depth 0时说明把s[i]翻转为)后s[1,i]中左括号仍比右括号多——这正是上文要求的$s[1,i-1]$ 中左括号数量大于右括号数量的等价条件depth 0表示后缀里右括号更多即前缀里左括号更多翻转后前缀盈余的左括号数为depth - 1于是后缀中需要open (n - i - 1 - depth) / 2个左括号和close n - i - 1 - open个右括号前者全部前置、后者全部后置保证字典序最小构造新串next s.substr(0,i) ) string(open,() string(close,))并交换若整个序列已经是字典序最大的合法括号序列形如(((...)))函数返回false表示不存在后继。以 $n3$ 的合法序列字典序枚举为例((())) (()()) (())() ()(()) ()()()从(())()出发扫描到下标 $i2$ 处的(时其后缀中右括号数更多满足条件将其翻转为)得到前缀())此时盈余 $k1$因此最后 1 个字符放)中间用(()填充得到()(())恰好是字典序中的下一个。5. 字典序计算求排名与反推序列5.1 问题定义给出合法括号序列 $s$要求出它在按字典序升序排列的长度为 $|s|$ 的所有合法括号序列中的排名。OI-wiki 给出的方法不是直接数出比 $s$ 大的序列而是数出所有字典序比 $s$ 小的括号序列 $p$ 的个数排名即等于这个数目加 $1$。5.2 转化为 DP 统计设 $p_i s_i$ 且 $\forall, 1\le ji,\ p_js_j$。由于左括号字典序最小$p_i$ 必为左括号而 $s_i$ 必为右括号。于是枚举 $i$满足 $s_i$ 为右括号假设 $p[1,i]$ 中左括号比右括号多 $k$ 个问题转化为统计长度为 $|s|-i$、存在 $k$ 个未匹配的右括号、且不存在未匹配的左括号的括号序列的个数。为此定义 DP 状态$f(i,j)$ 表示长度为 $i$、存在 $j$ 个未匹配的右括号、且不存在未匹配的左括号的括号序列的个数。5.3 转移方程枚举括号序列的第一个字符是什么第一个字符是右括号未匹配的右括号数从 $j-1$ 增加到 $j$即来自 $f(i-1,j-1)$第一个字符是左括号会与一个右括号抵消未匹配的右括号数从 $j1$ 减少到 $j$即来自 $f(i-1,j1)$。因此转移为$$ f(i,j)f(i-1,j-1)f(i-1,j1) $$初始条件 $f(0,0)1$其余 $f(0,j)0\ (j0)$。这个三角形数表实际对应 OEIS 中的 A053121 序列即所谓卡特兰三角形。利用该数组可以在 $O(|s|^2)$ 时间内完成字典序计算$|s|$ 是序列长度DP 表规模为 $O(|s|^2)$。5.4 变种括号序列的推广对于变种括号序列方法是类似的唯一的区别在于需要对每个 $s_i$ 枚举所有比它小的字符并分别累加。在原算法中由于朴素情况下不存在比左括号更小的字符所以只考虑了 $s_i$ 为右括号的情形而在变种场景下例如字符集存在、[、(等多级优先级时每个位置都可能有多于一个更小但可配对的选择需要对它们逐一用 $f$ 数组统计。5.5 由排名反推序列利用同一张 $f$ 数组我们也可以完成反向操作求字典序排名为 $k$ 的合法括号序列。做法是逐位确定字符——在当前位尝试放(若以(为前缀的合法序列总数可预先用 $f$ 数组算得不少于剩余需要跳过的排名 $k$则确定放(否则减去该数量、改放)如此循环直至填满整个序列。这本质上是数位 DP 逐位构造的标准技巧与上述统计过程互为逆运算。6. 小结与复杂度一览问题核心思想时间复杂度判定合法性贪心 栈扫描$O(n)$合法序列计数卡特兰数递推 / 通项公式$O(n)$ 或 $O(n\log n)$组合数字典序后继反向扫描找翻转点 最小字典序重构$O(n)$字典序排名DP 表 $f(i,j)$ 逐位统计$O(s^2)$由排名反推序列利用 $f$ 数组逐位构造$O(s^2)$本文涉及的算法均可在仓库中对应文档继续深挖括号序列计数的完整推导与多组合问题双射见 docs/math/combinatorics/catalan.md生成函数解法见 docs/math/poly/ogf.md卡特兰数的生成函数一节。此外括号序列思想在 OI-wiki 其他专题中也有广泛应用例如 伸展树维护括号序、动态树括号序维护 以及 DFS 序与括号序的结合可作为进一步学习的延伸方向。页首声明本页面核心内容主要译自博文 Balanced bracket sequences俄文原文与英文翻译版其中俄文版版权协议为 Public Domain Leave a Link英文版版权协议为 CC-BY-SA 4.0OI-wiki 在此基础上按自身排版与示例风格进行了整理与扩充。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考