题解：P12271 [蓝桥杯 2024 国 Python B] 括号与字母

A7F3jK9pR0xf_ · 2025-08-14 18:20:32 · 题解

题目传送门

红题。不知为何评绿？

先对每个字符做前缀和，令 s1_{i,j} 为前 i 个字符中出现小写字母表第 j+1 个字符的数量。这一步可以 O(|\sum|n) 处理，其中 \sum 是字符集。

接着用栈进行括号匹配，具体为：

• 若 s_i 为 ( 则将 i 入栈
• 若 s_i 为 ) 则将栈顶取出并删除栈顶

设每次取出栈顶元素为 cur，那么 s_{cur} 与 s_i 组成一对匹配的括号。此时小写字母表第 j+1 个字符在这对括号中间出现的次数为 s1_{i-1,j}-s1_{cur,j}，我们可以建一个桶 s2_{i,j} 来存储小写字母表第 j+1 个字符 恰好 出现 i 次的括号对数量，那么每算出一个括号对我们就对 s2 数组 O(|\sum|) 维护。

计算完 s2 数组后，不难发现每次所求答案即为 \sum_{i=x}^ns2_{i,c-'a'}，那么我们对 s2 做一次后缀和即可。这一步的复杂度依旧是 O(|\sum|n)，总复杂度为 O(|\sum|n)，注意 x 可能取 0 所以后缀和要做到下标 0。

代码很好写。