2021 CSP 题解
T2 括号序列
这应该是我遇到的最难的一道和括号有关的题了。
算法1
(暴力搜索) $O(n3^n)$
遇事不决,先打暴力。
枚举每一个 ?
的三种可能情况,最后判断是否满足要求。
即,相邻的 *
不能超过 $k$ 个,不能出现 (*A*)
、A*
或 *A
,后两种只有开头或结尾可能出现。
期望得分:15 分
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define q(t) q.top()
using namespace std;
const int N = 510, mod = 1e9 + 7;
int n, k, ans;
int num[N], t;
int f[N];
char a[N];
int check()
{
stack<int> q;
for (int i = 0, c = 0; i < n; i ++ )
{
if (a[i] == '*')
{
f[i] ++;
if (++ c > k) return 1;
}
else c = 0;
f[i + 1] = f[i];
}
if (a[0] == '*' || a[n - 1] == '*') return 2;
for (int i = 0; i < n; i ++ )
{
if (a[i] == '(') q.push(i);
if (a[i] == ')')
{
if (q.empty()) return 2;
if (a[q(t) + 1] == '*' && a[i - 1] == '*')
{
if (f[i - 1] - f[q(t)] != i - 1 - q(t))
return 2;
}
q.pop();
}
}
return q.size() ? 2 : 0;
}
void dfs(int u)
{
if (u >= t) {
if (!check()) ans ++;
return;
}
a[num[u]] = '(';
dfs(u + 1);
a[num[u]] = ')';
dfs(u + 1);
a[num[u]] = '*';
dfs(u + 1);
}
int main()
{
scanf("%d %d\n%s", &n, &k, a);
for (int i = 0; i < n; i ++ )
if (a[i] == '?')
{
num[t ++ ] = i;
}
if (check() != 1) dfs(0);
printf("%d", ans % mod);
}
算法二
(区间 Dp) $O(n^3)$
题目背景
一个长度为 n 且符合规范的括号序列,其有些位置已经确定了,有些位置尚未确定,求这样的括号序列一共有多少个。
分析
对于蒟蒻的博主而言,这道题的难度显然是犯规了的,但是,如果你能合理运用题目的条件,倒也能出奇制胜。
既然这道题写不出来,那就先看一下它的 弱化版。
通常对于一个求方案数的题目,只有两种算法可以解决,$DFS$ 和 $Dp$。
这道题数据量很大,那就只有可能是选 $Dp$ 了,那到底可以用哪种 $Dp$ 呢?
状压不行,数据量太大了,背包、树形、数位 似乎也不行。
不过,好像 状态机 跟这个有点关联,毕竟都有 多个状态 嘛,
这时,请注意一下 括号序列 的性质,多个 合法序列 正确组成的序列也是一个 合法序列。
到这里,答案已经呼之欲出了,没错 状态机思想 + 区间Dp。
所遇困境(以下分析都和弱化版无关)
但是不同的形态可能会有不同的转移,如:$(S)$ 这种只能从 $S$ 转移过来等等。所以只开两维的 $f$ 数组必然是不够的。
更何况 ?
似乎也没有办法处理?(事实上,只能先将它看成 万能牌 ,不再单独考虑。)
思考一下,既然这道题的状态太多了,那为何不能多开一维,用 状态机 的方式,将不同连边的状态 转换。
那我们还剩两个任务,设计状态、状态转移。
设计状态
我们可以发现,对于一个超级括号序列,一定可以表示成以下 七种形式:
$()$ 、$(S)$ 、$(AS)$ 、$(SA)$ 、$(A)$ 、$AB$ 、$ASB$。
而这 七种形式 又可以分成两类:
包在括号内的:$()$ 、$(S)$ 、$(AS)$ 、$(SA)$ 、$(A)$
首尾有两个括号序列的:$AB$ 、$ASB$
我们先尝试多开两位,用 $f[i][j][0]$ 和 $f[i][j][1]$ 分别表示上面这两类情况。
根据题意,$(S)$ 、$(AS)$ 、$(SA)$ 、$(A)$ 都是超级序列,所以我们要用 $S$ 、 $AS$ 、$SA$ 、$A$ 来对第一种情况的超级序列进行转移。
其中 $A$ 满足第一类的要求,但是 $S$ 、$AS$ 、$SA$ 显然都不符合,
因为它们代表三种不同的情况,所以需要再设计三种不同的状态来表示。
所有状态如下:
-
$f_{i,j,0}$ : 形态如
(...)
的括号序列(即左右直接被括号包裹且最左边括号与最右边的括号相互匹配)。 -
$f_{i,j,1}$ : 形态如
(...)***(...)*(...)
的括号序列(即左边以括号序列开头,右边以括号序列结尾)。 -
$f_{i,j,2}$ : 形态如
***...*
的括号序列(即全部是*,记得判断一下两端距离是否不大于 $k$)。 -
$f_{i,j,3}$ : 形态如
(...)**(...)***
的括号序列(即左边以括号序列开头,右边以*结尾)。 -
$f_{i,j,4}$ : 形态如
***(...)**(...)
的括号序列(即左边以*开头,右边以括号序列结尾)。
状态转移
请见代码(感觉会清晰一点)
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 510, mod = 1e9 + 7;
int n, k;
int f[N][N][5];
char s[N];
bool check(int l, int r)
{
return (s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?');
}
signed main()
{
scanf("%lld %lld %s", &n, &k, s + 1); // s 下标从 1 开始
for (int i = 1; i <= n; i ++ ) f[i][i - 1][2] = 1;
for (int len = 1; len <= n; len ++ )
for (int l = 1, r; (r = l + len - 1) <= n; l ++ )
{
f[l][r][2] = f[l][r - 1][2] & (s[r] == '*' || s[r] == '?') & (len <= k);
// 需满足仅由*构成且不超过k个, 因为*都是一样的, 所以值只存在1和0两种可能
if (len == 1) continue; // 当len等于1时, 除f[l][r][2]以外的都只能为0
f[l][r][0] = check(l, r) * (f[l + 1][r - 1][0] + f[l + 1][r - 1][1] + f[l + 1][r - 1][2] + f[l + 1][r - 1][3] + f[l + 1][r - 1][4]) % mod;
// 如果s[l]和s[r]可以组成一个括号的话
for (int k = l; k < r; k ++ ) // 分成[l, k]和[k + 1, r]
{
// AS -> ASB / A + S
f[l][r][3] = (f[l][r][3] + (f[l][k][0] + f[l][k][1]) * f[k + 1][r][2]) % mod;
// f[l][k][0] 和 f[l][k][1] 之间,只有一个是有效的。
// 由乘法原理可知, AS 方案数 = A 方案数 * S 方案数, 总方案数需要累计
// SA -> S + ASB / A
f[l][r][4] = (f[l][r][4] + (f[k + 1][r][0] + f[k + 1][r][1]) * f[l][k][2]) % mod;
// f[k + 1][r][0] 和 f[k + 1][r][1] 之间,只有一个是有效的。
// 由乘法原理可知, SA 方案数 = A 方案数 * S 方案数, 总方案数需要累计
// AB/ASB -> ASB / A / AS + A
f[l][r][1] = (f[l][r][1] + (f[l][k][0] + f[l][k][1] + f[l][k][3]) * f[k + 1][r][0]) % mod;
// 由乘法原理可知, AB 方案数 = A 方案数 * B 方案数, 总方案数需要累计
// 由乘法原理可知, ASB 方案数 = AS 方案数 * B 方案数, 总方案数需要累计
}
}
printf("%lld", (f[1][n][0] + f[1][n][1]) % mod); // 任选一个
}