括号问题

Published: by Creative Commons Licence

  • Tags:

括号数目统计

要计算长度为$n$的有效括号对数目,可以通过卡特兰数来计算。

数量为:

\[{2n\choose n} - {2n \choose n + 1}\]

交错括号问题

给定两类括号$()$和$[]$。一个合法的括号序列$s$有如下几种:

  • $s$是空串
  • $s=(a)$,其中$a$是合法括号序列
  • $s=[a]$,其中$a$是合法括号序列
  • $s=ab$,其中$a$和$b$都是合法括号序列

题目1:长度为$n$的01字符串有多少,满足将0替换为圆括号,将1替换为方括号,有机会得到一个合法的括号序列。

首先$n$如果是奇数,那么结果一定是$0$,接下来我们假定$n$是偶数。

考虑由$0$占领的下标,记录$a$为其中奇数的数目,$b$为其中偶数的数目。可以发现如果$a\neq b$,则必定会出现相同奇偶性下标配对的情况(此时其中留给方括号的长度为奇数),这时候是不可能产生号字符串的。因此$a=b$是有解的前提。

接下来我们说明如果$a=b$一定有解。实际上我们可以不断找到两个相邻的0出现的下标(忽略1出现的位置),其中一者是偶数,另外一者是奇数。之后我们将它们配对,并删除。重复这个过程我们就可以将$0$替换为圆括号。之后对$1$的替换就非常简单了。

因此答案为$\sum_{i=0}^{n/2} {n/2\choose i}^2$。

题目2:给定长度为$n$的序列$a$和序列$b$,之后要求找到一组权值最大的合法字符串。如果字符串的第$i$个字符是圆括号,则该位置的权值为$a_i$,否则为$b_i$,字符串的总权值就是所有位置的权值之和。其中$n$为偶数。

首先我们可以将所有位置都放置为方括号,之后我们考虑将一些位置替换为圆括号,我们定义$c_i=a_i-b_i$。

在题目1中我们已经讨论过圆括号中奇数下标和偶数下标数量相同是存在一种方案的等价条件。因此我们可以不断找到权重$c$最大的奇数下标和偶数下标$i,j$,如果$c_i+c_j\gt 0$,则将这两个下标替换为圆括号并重复流程,否则退出流程。

提供一道题目