1. 先把题目读懂什么是“永远在一起”上个月我们这边打了一场月赛T2 就是这道 P15445题面起了个非常文艺的名字叫“永远在一起”。我当时看到这个名字愣了一下读完题意才发现它本质上是在问括号匹配的问题给你一个只包含(和)的字符串统计里面有多少个连续子串是合法的括号序列。为什么叫“永远在一起”呢你可以这么理解一对左右括号一旦匹配成功它们的位置关系就固定了中间不能再被拆散而一个合法的括号子串就是一段内部所有括号都“成双成对、永不分离”的区间。先把题意整理成下面这个版本方便后面推导给定一个长度为 n 的字符串 ss 中只包含(和)。 统计 s 中所有连续子串里有多少个是合法括号序列。 合法括号序列的定义就是标准的括号匹配空串合法若 A 合法则(A)合法若 A、B 合法则 AB 合法。 数据范围n ≤ 10^6答案可能很大需要用 64 位整数存储结果不需要取模。这道题适合两类人看一类是刚学完栈和动态规划想看看这两个东西怎么配合的初学者另一类是准备算法竞赛想练一练“把暴力观察转化成线性 DP”思维的选手。我当时在考场上第一反应是“这题拿个栈扫一遍不就行了”结果写着写着发现不对劲传统的括号匹配只是判断整个串是否合法而这题要求数出所有合法子串的数量这两件事差得还挺远的。后来冷静下来重新分析才找到了比较漂亮的线性做法。这篇博客就把完整的思路、推导、代码、坑位一次讲清楚。1.1 先明确一个容易混淆的点很多人在读题的时候会下意识把“合法子串”理解成“合法连续区间”这没问题但要注意它和“匹配对数”的区别。比如()()这个串它有 4 个合法子串吗不对你数一下第一个()下标 1 到 2第二个()下标 3 到 4整个()()下标 1 到 4一共 3 个。注意空串不算所以不能把空串数进去。这个例子告诉我们不能只统计有多少个“括号对”因为相邻的合法段会拼成新的合法子串。这个“拼接”性质是整个 DP 的核心也是暴力做法容易漏算或者重复算的地方。1.2 题目本质是什么把合法括号子串这个事情翻译一下其实就是一个区间[l, r]满足三个条件s[l] (且s[r] )要不然不可能合法区间内左括号和右括号数量相等区间任意前缀中左括号数量不少于右括号数量。第 1 和第 2 条都好理解第 3 条是括号序列的“前缀非负”性质也就是扫描过程中永远不能让右括号比左括号先多出来。这个必要条件可以独立判断但是直接拿它去枚举区间复杂度是下不来的。所以问题的难点在于怎么把“所有区间”这个指数级或平方级的概念压缩成线性扫描可以维护的东西。2. 从暴力到正解两种思路的取舍2.1 暴力枚举拿到部分分很简单先不要急着上正解暴力枚举是最直观的起点。最简单的写法是枚举左端点l然后向右扩展右端点r用一个计数器cnt来维护当前区间[l, r]内左右括号的差值遇到(cnt遇到)cnt--如果cnt 0说明这个左端点往后的区间都不可能合法了直接剪枝跳出如果cnt 0就说明区间[l, r]合法答案加一。这个暴力的时间复杂度是 O(n^2)因为枚举了所有左端点和右端点。n ≤ 500的点能轻松过n ≤ 2000的点用剪枝也能勉强跑。但如果数据范围升到10^6这个复杂度是不可接受的。不过暴力代码有一个非常大的作用它可以当对拍器。写正解之前先写一个暴力版本生成随机小数据去验证正解的正确性。这个习惯在考场上能救你命后面我会细说。2.2 为什么不能用前缀和直接搞定很多人会想我用前缀和数组pre[i]表示前 i 个字符里(的数量减去)的数量然后判断区间[l, r]是否合法就只需要看pre[r] - pre[l-1] 0。这样 O(1) 判断数量相等不就能 O(n^2) 枚举了吗这个思路的一半是对的。前两条条件的确认可以用前缀和做到 O(1)但第三条“任意前缀不低于左端点”做不到。举个例子s )(()前缀和数组自己算一下pre[0] 0pre[1] -1 读到)减 1pre[2] 0 读到(pre[3] 1 读到(你要判断区间[2, 2]pre[2]-pre[1] 0 - (-1) 1这不是 0不合法没问题。但区间[3, 3]也是一个(也不合法。再看区间[1, 2]这一段的 pre 差值是pre[2]-pre[0] 0 - 0 0数量相等但它是)(显然不合法因为第一个字符就是右括号。所以只靠前缀和做差值完全无法捕捉“区间内部某个前缀变成负数”的信息。你必须额外维护区间最小值而这是一个范围查询问题用单调栈或线段树可以做但复杂度已经上去了而且代码复杂度很高。月赛 T2 通常不该用这么重的数据结构这说明肯定有更简单的方法。2.3 核心观察合法子串可以按“右端点”分类我最后想到的方法是分而治之按右端点分类只统计以每个位置 i 结尾的合法子串数量最后累加。设dp[i]表示以s[i]结尾的合法括号子串的数量。如果s[i] (那不可能有以它结尾的合法子串因为合法括号序列一定以)结尾所以dp[i] 0。如果s[i] )它必须先找一个左括号跟它配对。这个左括号是哪个用栈来维护。这里的关键是栈里存的不是字符而是下标。每遇到一个(就把它的下标压入栈每遇到一个)且栈不为空就弹出栈顶下标记为m表示s[m]和s[i]配成了一对。当这一对匹配成功后我们得到了一个以s[m]开头、s[i]结尾的合法括号对也就是子串s[m...i]。但合法子串不止这一个。如果m-1的位置也是一个合法段的结尾那s[m...i]前面接上那一整段拼起来的整体也仍然是一个合法括号序列。比如()()里第二个)匹配的m 3而m-1 2恰好是以s[2]结尾的合法段()的结尾于是拼接成()()也是合法子串。所以递推式就出来了dp[i] dp[m - 1] 1其中m是与s[i]匹配的左括号下标。为什么加 1因为s[m...i]本身就是一个合法的括号对它是一个新的、只算一次的合法子串。dp[m-1]能提供的是所有能拼接到这一对前面的合法段数量。两者相加正好是所有以 i 结尾的合法子串数。还是拿()()验证。s[2] 匹配 m1dp[2] dp[0] 1 1对应(1,2)。s[4] 匹配 m3dp[4] dp[2] 1 2对应(3,4)和(1,4)。加起来是 3和手数一致。2.4 再往前一步连续的合法括号段上面这个 DP 本质上已经把“拼接”处理掉了但它背后还有一个更朴素的视角我们可以把原串划分成若干个“连续的合法括号段”。比如()(())整体是一个合法段。如果我们把这个串拆开看(())内部又嵌了一个()。这个嵌套关系在栈匹配的过程中会自然浮现出来而 DP 公式里的dp[m-1] 1正好是在处理嵌套和拼接两种情况的统一表达。当你遇到内层的)先匹配成功再遇到外层的)匹配成功外层的dp dp[内层配对的前一个位置] 1这个加 1 对应的就是外层的那个最大的括号对。嵌套和拼接通过同一个公式被统一了这就是这题最精妙的地方。3. 完整代码实现30分钟能写完的 AC 代码3.1 核心代码C17 注释版先把正解代码贴出来。整体非常短核心循环就十几行。#include bits/stdc.h using namespace std; const int MAXN 1e6 5; char s[MAXN]; long long f[MAXN]; int stk[MAXN]; int main() { int n; scanf(%d, n); scanf(%s, s 1); int top 0; long long ans 0; for (int i 1; i n; i) { if (s[i] () { stk[top] i; f[i] 0; } else { if (top 0) { f[i] 0; } else { int m stk[top--]; f[i] (m 1 ? f[m - 1] : 0) 1; ans f[i]; } } } printf(%lld\n, ans); return 0; }这个代码有几个细节值得停下来看stk数组手写栈效率比std::stack高一点而且下标访问方便调试也直观。f[i]只在实际匹配成功的时候才更新。匹配失败或者遇到(时f 保持 0不参与答案累计。m是配对的左括号下标m - 1必须大于 0 才去查f[m-1]否则越界。3.2 代码各部分的职责拆解先看压栈分支遇到(直接把当前位置压进去同时把f[i]置 0。因为任何以左括号结尾的合法子串数量都是 0后续匹配成功时需要用这个位置作为m。再看弹栈分支遇到)先检查栈是不是空的。如果空说明这个右括号没有可配对的左括号那么以它结尾的合法子串数量就是 0后续也没必要继续操作。如果栈不空弹出栈顶得到m。注意这里m一定小于当前i并且s[m]一定是(。此时我们不仅确定了一个新的配对还可能顺着这个配对往前拼接。f[m - 1]的含义要再说清楚它表示的是所有以s[m-1]结尾的合法子串数。m-1这个位置有两种可能如果s[m-1]是)那它可能属于一个合法段的结尾此时f[m-1]不为 0于是(s[m-1]之前的合法段) s[m...i]就拼成一个更长的合法子串。如果s[m-1]是(或者不存在那么f[m-1]是 0不会产生错误拼接。这个设计的巧妙之处就是把“前面的合法内容”全部压缩成一个数值避免了在匹配成功后再回头扫描一遍前面的内容从而把整体复杂度压到了线性。3.3 验证样例与边界测试不要拿到代码就提交先在本地跑几组数据。第一组就是刚才说的()()4 ()()运行过程手动推一下i1s[1](压入 1i2s[2])弹出 m1f[2] f[0] 1 1ans1i3s[3](压入 3i4s[4])弹出 m3f[4] f[2] 1 1 1 2ans3输出 3正确。第二组测一个嵌套(())4 (())i1压入 1i2压入 2i3s[3])弹出 m2f[3] f[1] 1 0 1 1ans1i4s[4])弹出 m1f[4] f[0] 1 0 1 1ans2这里注意以 s[3] 结尾的合法子串是(2,3)以 s[4] 结尾的合法子串是(1,4)。总共 2 个和手数一致。第三组测一个交错但不完全匹配的串())(()6 ())(()i1压入 1i2弹出 m1f[2]1ans1i3s[3])栈空f[3]0i4压入 4i5压入 5i6弹出 m5f[6]f[4]1011ans2最终答案 2正确子串(1,2)和(5,6)。我建议你把这些样例都亲手推一遍尤其是第二组的嵌套例子推完了基本就理解dp[m-1]在干什么了。4. 踩坑记录与常见问题排查4.1 栈里到底存什么很多人会存成字符有人一看到括号匹配条件反射就写一个stackchar存(和)。在这个题里如果你只存字符匹配成功之后根本拿不到左括号的下标mf[m-1]自然没法计算。所以你必须在栈里存下标而不是字符。这也是我常常跟人强调的栈只是工具存的内容取决于你后续需要什么。题目只要求判断合法性时存字符就够题目要求统计区间或子串时优先考虑存下标。4.2 答案要用 long long别用 int这个很多人会踩。n 最大可以到 10^6理论上最坏情况是类似于()()()...这样到处都能拼接的串合法子串数量是 O(n^2) 的规模。你自己算一下()()()...()这种连续拼接串以每个)结尾的 dp 值是 1、2、3、...、n/2累加起来大约是 n^2/8 级别。n10^6 时这个值超过 10^11已经远超出int范围。所以答案必须用long longf数组也必须用long long。有些人在 dp 数组上用了 int小数据没事一上大数据就 WA检查半天找不到错最后发现是溢出特别憋屈。4.3 别忽略m 1这个边界判断f[m-1]在这里如果你写成f[m - 1]而不判断m 1那f[0]是有定义的因为数组下标 0 存在且初始化是 0所以不会越界。但是在一个测试点里如果你把字符串从下标 1 开始存f[0]是全局数组自动初始化为 0所以直接写f[m - 1] 1其实也不会出错。不过如果你的写法是dp[i] dp[m - 1] 1并且 m 恰好是 1那dp[0]就代表“空串”它是一个合法的空括号序列。从 DP 语义上这里取 0 或 1 会有区别。有人可能会想空串也算合法括号序列dp[m-1]是不是应该加 1 表示空串也要算进去这里要小心题目要求统计连续子串空串不是字符串的子串。我们在dp[i]的定义里统计的是“以 s[i] 结尾的合法子串数量”这个“子串”要求非空。所以当m 1时dp[0] 0表示前面没有任何合法段可以拼接只有s[m...i]这一个新子串。4.4 为什么不能简单地“遇到一对就加一”我见过不少人的思路是每次遇到一对匹配的括号ans最后输出 ans。这在()()这种串上会输出 2但正确答案是 3漏掉了拼接出来的整个串。还有人用另一种做法维护当前连续合法括号段的长度cnt遇到匹配就cnt 2然后ans cnt / 2。这个思路比朴素的想法好一点能处理部分拼接但它只适用于“当前位置处于一个连续合法段内部”的情况遇到嵌套和并列混合的串就会算错。比如()(())用这种思路( )匹配cnt2ans1( ( ) )中间内层匹配时 cnt2ans1外层匹配时 cnt4ans2最后得 4。但正确答案是几个(1,2)、(3,6)、(4,5)、(3,6) 前面拼接 (1,2)也就是(1,6)。所以是 4 个。这里巧合正确但换一个交错的情况就会出问题())(()用这个思路算也会出错因为中间断开的))处理不干净。一句话总结长度法只适合连续的单一合法段不适合有间隔和嵌套的杂串。4.5 内存优化f 数组可以滚动省掉吗f[i]的更新依赖f[m-1]而m-1是 i 之前的一个位置不一定是 i-1。所以你不能只保留一个滚动变量。最坏情况下()()()...里每个)匹配到的是上一个(它们可能相隔很远。但你没发现一个模板吗这个问题的stk本身其实就承担了一部分“记忆”功能。f[m-1]的值在匹配成功的一瞬间才会被用到理论上可以用一个辅助数组只存“以某个位置结尾的合法子串数”这个数组是必须要有的因为可能在很远之后才被引用。所以f数组没办法省掉。好在数组内存不大f用long long最多 8MBstk用int最多 4MB总共 12MB完全能接受。5. 复杂度分析与同型题目扩展5.1 时间复杂度和空间复杂度时间上每个字符只被扫描一次每个左括号入栈一次、出栈一次。f数组的更新是 O(1)。所以整体是 O(n)。空间上需要f[MAXN]和stk[MAXN]都是 O(n)。这题能做到 O(n)本质是因为我们在“按右端点分类”之后每个右端点只需要知道它匹配的左括号位置以及那个位置之前的合法段数量这两个信息都能在扫描过程中 O(1) 得到。没有 log没有二分就是一个单调的栈和一个一维 DP。如果 n 增加到 10^7这个算法照样能跑只是输入输出的常数需要优化。如果数据范围扩大到多组数据每组求一次 O(n)总复杂度就是 O(总长度)也完全没问题。5.2 进阶方向一带通配符的括号序列如果题目把部分字符改成?表示可以当作左括号或右括号让你统计所有可能的替换方案对应的合法子串总数那 DP 状态就得多一维。因为替换方案不同匹配结果也不同不能只用一个栈了。常见的处理思路是把问题转化成“最小替换数”或者“方案数”的 DP状态为dp[i][j]表示处理到第 i 个字符、栈中剩余 j 个左括号的方案数或数量。这种题型在动态规划里是独立的版块和今天的单串扫描并不是一个难度。但理解了今天的基础模型再去学那类问题会更快。5.3 进阶方向二最长合法括号子串经典的 LeetCode 32 题“最长有效括号”和这个题非常像只是问的是长度而不是数量。那道题的 DP 设计是遇到)且匹配成功dp[i] dp[m-1] (i - m 1)连续拼接时还要考虑跨过匹配段之前的合法长度最后取最大值两道题共用同一个“栈匹配 dp 拼接”思想只是目标函数从“计数”换成了“求最大值”。如果你能把今天这道题完全吃透再去写 LeetCode 32十分钟内就能写出来因为核心递推式子几乎就是同一个。5.4 进阶方向三二维括号矩阵里的矩形子区域如果把字符串拉长成一个 2D 括号矩阵问你多少个矩形区域内按行拼接后是合法括号序列那就要把每一列的符号转成“某一行的括号差值”然后用单调栈处理“列之间的最小前缀和”。这种题已经达到区域赛铜牌难度了。做这种题之前你必须先具备今天这种“把一个区间合法性压缩成一个可拼接数值”的思维否则面对二维问题根本无法建模。最后说点题外话这道 P15445 我打完之后最大的感受是它一点都不难但它非常“诚实”。你一旦没想清楚“合法子串既能嵌套又能拼接”这件事写出来的代码一定在某些刁钻数据上挂掉。我后来拿它去和别人对拍发现最常见的错误就是只处理了嵌套没处理拼接或者反过来。所以如果你在比赛里遇到这种“题面很短、代码很短、但坑很多”的计数题我建议你多花五分钟手写小数据验证别急着交。数据结构写挂了还能调算法模型没想清楚再调也是白调。这道题的扩展空间很大能演化出很多变体。但核心就一句话用栈找到配对用 dp 记住前面的合法段计数就完成了。下次再看到“永远在一起”类似的意象第一时间往括号匹配上想大概率不会错。