2025-10-30 微模拟

只有一道题，考场得分 $40pts$ 。考场上漏写了几种分类讨论（~~样例太少导致的~~），实际上思路已经想对了。

括号计数

给你一个长为 $n$ 的不完整的括号串 $S$ ，由这些字符构成：()[]{}<>?。前面八个是确定的括号，? 是占位符，表示未确定的符号。现在需要你求出一共有多少种可能的合法括号串。

例如，???)(? 有 8 种可能。

合法括号串的形式化定义：

()、[]、{}、<> 是合法括号串。
如果 $A$ 是合法括号串，那么 $pAq$ 是合法括号串，其中 $p,q$ 是一对相匹配的括号。
如果 $A,B$ 是合法括号串，那么 $AB$ 是合法括号串。

范围： $1\le n\le30.$

思路

这道题可以区间 DP，也可以记忆化搜索。我个人感觉记忆化好写一点。下面我们设计 int dfs(int l, int r)，表示 $[L,R]$ 上合法括号串的方案总数。

题目所给的两种合法括号串的构造方法给了我们启发。不妨考虑，如果当前串 $[L,R]$ 是合法的括号串，会有几种情况？

$S_L$ 和 $S_R$ 相配对，并且 $[L+1,R-1]$ 是合法的括号串。
$[L,R]$ 可以由两个合法的子括号串 $[L,k],[k+1,R]$ 拼接而成。

没有别的情况了。所以我们对应这两种情况进行搜索，用 res 记录当前区间 $[L,R]$ 的答案：

对于情况一：如果 $S_L$ 可能 $S_R$ 相配对，就向下递归：
- 如果两边都是 ?，令 res += 4 * dfs(l+1, r-1)。
- 如果两边的括号是确定的，令 res += dfs(l+1, r-1)。
对于情况二：枚举分割点 $k$ ，尝试分割：res += dfs(l, k) * dfs(k+1, r)。如果此处不能进行分割，自然会有一个 dfs() 返回 0，对答案无影响。

这对吗？对于情况二，考虑以下串：

_ _ _ _ x _ _ _ _ y _ _ _ _

其中 x，y 表示可能的分割点，而 _ 处不能被分割。dfs() 时，有可能：

上层 dfs() 在 x 处分割，下层右边 dfs() 在 y 处分割。
上层 dfs() 在 y 处分割，下层左边 dfs() 在 x 处分割。

这样，同样的分割情况被我们计算了两次。如何去重？不妨在 dfs() 添加新的一个参数：int dfs(int l, int r, bool allowDivide)。当我们尝试分割时，令左边的子串不许分割，即 res += dfs(l, k, false) * dfs(k+1, r)，这样就可以去重了。

这样写肯定会 TLE 的。如何优化？我们建立一个记忆化数组 mem[][][]，每次 dfs() 返回的时候存入搜索结果；dfs() 开始时，我们先从 mem[][][] 中检索，如果已经搜过了，就直接使用保存的结果。这样就可以 AC 了。

编码

注意一下 unsigned long long 要用 %llu 输出（而不是 %lld）

用时 17ms 内存 536 KB

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 30;
char s[MAXN + 1];

bool isOpen(char c) { return c == '(' || c == '[' || c == '{' || c == '<'; }
bool isClose(char c) { return c == ')' || c == ']' || c == '}' || c == '>'; }
bool isPair(char a, char b) {
    return (a == '(' && b == ')') ||
        (a == '[' && b == ']') ||
        (a == '{' && b == '}') ||
        (a == '<' && b == '>');
}

ull mem[MAXN][MAXN][2];

ull dfs(int l, int r, bool allowB = true) {
    if (mem[l][r][allowB] != 0) {
        return mem[l][r][allowB] - 1;
    }
    // 特判
    if (l + 1 == r) {
        if (s[l] == '?' && s[r] == '?') return 4;
        if ((isOpen(s[l]) && s[r] == '?') ||
            (isClose(s[r]) && s[l] == '?') ||
            isPair(s[l], s[r])) {
            return 1;
        }
        return 0;
    }
    ull res = 0;
    // 情况 I
    if (s[l] == '?' && s[r] == '?') res += 4 * dfs(l + 1, r - 1);
    if ((isOpen(s[l]) && s[r] == '?') ||
        (isClose(s[r]) && s[l] == '?') ||
        isPair(s[l], s[r])) {
        res += dfs(l + 1, r - 1);
    }
    if (!allowB) {
        mem[l][r][allowB] = res + 1;
        return res;
    }
    // 情况 II
    for (int i = l; i < r; i++) {
        if (i > l) {
            res += dfs(l, i, false) * dfs(i + 1, r);
        }
    }
    mem[l][r][allowB] = res + 1;
    return res;
}
int main() {
    freopen("bracket.in", "r", stdin);
    freopen("bracket.out", "w", stdout);
    scanf("%s", s);
    int n = strlen(s);
    printf("%llu", dfs(0, n - 1));
    return 0;
}

时间复杂度

对于每个状态 $(L,R,\text{allowDivide})$ ，情况一的复杂度为 $O(1)$ ，情况二为 $O(n)$ 。一共有 $n^2$ 个状态，每种状态只会被搜到一次，所以时间复杂度似乎是 $O(n^3)$ 。

依旧随机括号串测试，却发现时间复杂度约为 $O(n^2)$ 。下面设搜索次数为 $T$ ，问题规模为 $n$ 。

$T-n$ 图像

$T/n-n$ 图像

上图中蓝色的点的数据是全为 ? 的括号串（最坏情况），红色的点是 $50\%$ 的 ? 与 $50\%$ 的随机括号。

括号计数​

思路​

编码​

时间复杂度​

括号计数

思路

编码

时间复杂度