题解：P10161 [DTCPC 2024] 小方的疑惑 10

_jxy · 2025-03-27 13:50:32 · 题解

考虑这样一个字符串如何计算它有多少个子串为合法的括号序列：

()(()()())((()))

答案为 \frac{3 \times 4}{2} + \frac{3 \times 4}{2} + \frac{1 \times 2}{2} + \frac{1 \times 2}{2} = 14。

这个时候，我们意识到一个重要结论：只有不在括号内或者在同一个括号内的括号，才能组合计算贡献。假设有 n 个括号能组合计算贡献，它的贡献是 \frac{n \times n+1}{2}。

这很好理解，比如：

(()()())

中间的三对括号被包围在最外面的括号当中，它们三个的贡献之和为 \frac{3 \times 2}{2} = 3。

最外层的括号没有在任何括号内部，所以它的贡献就是 \frac{1 \times 2}{2} = 1。

知道了这个以后，直接和其他题解一样 dp 之后构造就好了，如果长度不够的话，直接在后面加右括号，显然不会对答案产生任何影响。