发表更新学习笔记

括号模型题的简单概括

((想)((不出)骚*)话了)

Prelude

合法括号串的定义如下：

  1. () 是合法括号串。
  2. 如果 A 是合法括号串，则 (A) 是合法括号串。
  3. 如果 A，B 是合法括号串，则 AB 是合法括号串。

XCPC 中经常会出现一些括号序列类的问题，这类问题在最开始的思考上一般是具有普遍共性的。常见的思考一般是：把 ( 看成 $+1$，把 ) 看成 $-1$。对于整个括号序列求前缀和 $p_i$，那么就有以下几条限制：

  • $p_i \geq 0$，也就是不存在任意一个位置使得右括号的数量大于左括号的数量
  • $|p_i - p_{i-1}| = 1$，这个显然。

然后通过这两个公式的转化，括号类问题又变成序列类问题，再上各种各样的算法去解决他们。当然还有一种比较经典的括号问题就是括号序列 DP。这个在下面的例题会讲到。以及最最传统的用栈去求一组合法匹配这种题。

例题1.[CSP-S2019] 括号树

一个大小为 $n$ 的树，树上结点从 $1 \sim n$ 编号，$1$ 号结点为树的根，$i$ 号结点的父亲为 $f_i$。

小 Q 发现这个树的每个结点上恰有一个括号，可能是( 或)。小 Q 定义 $s_i$ 为：将根结点到 $i$ 号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。

显然 $s_i$ 是个括号串，但不一定是合法括号串，因此现在小 Q 想对所有的 $i$（$1\leq i\leq n$）求出，$s_i$ 中有多少个互不相同的子串是合法括号串。

$n \leq 5\times 10^5$

这个题其实是一个树形 DP 题，但是因为和括号结合起来了看着有点变态。思考一下，我们现在考虑 $s_i$ 从哪里来，显然考虑 $[1,i]$ 这一段的括号序列实际上是可以由 $[1,f_i] $ 转移过来的。我们可以用 $s_i$ 这一位的括号来匹配掉之前存在的括号，以此产生新的子串。

难点在于维护新增子串这里，具体来说，我们需要像做一个最普通的子串匹配一样，用一个栈 $st[x]$ 来保存到节点 $x$ 的匹配情况，接下来我们讨论一下：

  • $s_i = ($ ，这里显然不会和之前的新增任何子串，影响为 0.
  • $s_i = )$，这里还有两种讨论方法，
    • 若栈为空，那么显然没有任何讨论价值。
    • 若栈非空且栈顶可以匹配，我们可以写出递推式 $dp_x = dp[f[st[top]] + 1$，这个递推式的含义是考虑从匹配那个点的转移过来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
	int v = getchar();T f = 1;t = 0;
	while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
	while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
	t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
	read(t);read(args...);
}

const int N = 5e5 + 10;

ll n,st[N],top,f[N],fat[N],sum[N];
vector <int> G[N];
char s[N];

void dfs1(int x,int fa) {
	int las = 0;
	fat[x] = fa;
	if (s[x] == '(') st[++top] = x,las = -1;
	else {
		if (top) {
			las = st[top];--top;
			f[x] = f[fat[las]] + 1;
		}
	}
	for (auto y : G[x]) {
		if (y != fa) {
			dfs1(y,x);
		}
	}
	if (las == -1) --top;
	else {
		if (las != 0) st[++top] = las;
	}
}

void dfs2(int x,int fa) {
	sum[x] = sum[fa] + f[x];
	for (auto y : G[x]) {
		if (y != fa) dfs2(y,x);
	}
}

signed main() {
	scanf("%lld\n",&n);
	scanf("%s",s+1);
	for (int i = 2;i <= n;++i) {
		int x;read(x);
		G[x].push_back(i);G[i].push_back(x);
	}
	dfs1(1,0);dfs2(1,0);
	ll ans = 0;
	for (ll i = 1;i <= n;++i) ans ^= (i * sum[i]);
	printf("%lld\n",ans);
	return 0;
}

例题2.[CSP-S 2021] 括号序列

小 w 在赛场上遇到了这样一个题：一个长度为 $n$ 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。

身经百战的小 w 当然一眼就秒了这题，不仅如此，他还觉得一场正式比赛出这么简单的模板题也太小儿科了，于是他把这题进行了加强之后顺手扔给了小 c。

具体而言，小 w 定义“超级括号序列”是由字符 (、)、* 组成的字符串，并且对于某个给定的常数 $k$，给出了“符合规范的超级括号序列”的定义如下：

  1. ()、(S) 均是符合规范的超级括号序列，其中 S 表示任意一个仅由不超过 $k$ 个字符 * 组成的非空字符串（以下两条规则中的 S 均为此含义）；
  2. 如果字符串 A 和 B 均为符合规范的超级括号序列，那么字符串 AB、ASB 均为符合规范的超级括号序列，其中 AB 表示把字符串 A 和字符串 B 拼接在一起形成的字符串；
  3. 如果字符串 A 为符合规范的超级括号序列，那么字符串 (A)、(SA)、(AS) 均为符合规范的超级括号序列。
  4. 所有符合规范的超级括号序列均可通过上述 3 条规则得到。

例如，若 $k = 3$，则字符串 ((**()*(*))*)(***) 是符合规范的超级括号序列，但字符串 *()、(*()*)、((**))*)、(****(*)) 均不是。特别地，空字符串也不被视为符合规范的超级括号序列。

现在给出一个长度为 $n$ 的超级括号序列，其中有一些位置的字符已经确定，另外一些位置的字符尚未确定（用 ? 表示）。小 w 希望能计算出：有多少种将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个符合规范的超级括号序列？

$1 \le k \le n \le 500$。

神人题，但是也很经典。本质上这种括号序列 + DP 的题都是要把答案的形态考虑明白，然后再进行转移。

我们考虑以下几种答案状态：

  1. (...) 左右端自我匹配，这种记为 $f_{i,j}$
  2. (...)...(...) 左右端匹配，但是这俩本身并不匹配，这种记为 $g_{i,j}$
  3. (SA) 这种单独讨论一下，主要问题是判断 S，这种记为 $SA_{i,j}$，然后 (AS) 本质上也是一样的，其实这两种都可以规约到 $f$ 里面，就是转移的时候需要注意一下。
  4. ASB 和 AB 需要特别注意，当然这两种还是很简单的。

具体方程讨论太长了有点懒得敲，还是直接看 code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
	int v = getchar();T f = 1;t = 0;
	while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
	while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
	t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
	read(t);read(args...);
}

const int N = 510;
const ll mod = 1e9 + 7;
char s[N];
ll f[N][N],p[N][N],g[N][N],SA[N][N],n,k;

bool checks(int pos) {return s[pos] == '*' || s[pos] == '?';}
bool checkl(int pos) {return s[pos] == '(' || s[pos] == '?';}
bool checkr(int pos) {return s[pos] == ')' || s[pos] == '?';}

signed main() {
    scanf("%lld %lld\n",&n,&k);
    scanf("%s",s+1);
    for (int i = 1;i <= n;++i) {
        if (!checks(i)) continue;
        p[i][i] = 1;
        for (int j = i + 1;j <= min(n,i + k - 1);++j) {
            if (!checks(j)) break;
            p[i][j] = 1;
        }
    }
    for (int len = 1;len <= n;++len) {
        for (int l = 1;l + len <= n;++l) {
            int r = l + len;
            //printf("%d %d\n",l,r);
            if (len == 1) {
                if (checkl(l) && checkr(r)) f[l][r] = g[l][r] = 1;
                continue;
            }
            if (checkl(l) && checkr(r)) {
                f[l][r] = (f[l][r] + f[l + 1][r - 1]) % mod;
                f[l][r] = (f[l][r] + p[l + 1][r - 1]) % mod;
                for (int k = l + 1;k < r - 1;++k) f[l][r] = (f[l][r] + p[l + 1][k] * f[k + 1][r-1] % mod) % mod;
                for (int k = l + 1;k < r - 1;++k) f[l][r] = (f[l][r] + f[l + 1][k] * p[k + 1][r-1] % mod) % mod;
                
            }
            g[l][r] = f[l][r];
            for (int k = l;k < r;++k) SA[l][r] = (SA[l][r] + p[l][k] * g[k+1][r] % mod) % mod;
            for (int k = l;k < r;++k) f[l][r] = (f[l][r] + f[l][k] * g[k + 1][r] % mod) % mod;
            for (int k = l;k < r;++k) f[l][r] = (f[l][r] + f[l][k] * SA[k + 1][r] % mod) % mod;
            //printf("%d %d\n",f[l][r],g[l][r]);
        } 
    }
    printf("%lld\n",f[1][n]);
	return 0;
}

例题3.SHCPC2022 Bracket Query

我承认是为了这碟醋才包这碟饺子的

这个题就是特别经典的利用前缀和转化了，题目给的条件实际上可以转化为 $p_r - p_{l-1} = x$，那么这个条件有一个好，就是特别方便建出差分约束的图（当然使用带权并查集也可以）

求出差分约束之后，我们知道因为一组差分约束的序列 $X$ 可以同时加上偏移量 $\Delta$ 从而使得同样成立，我们实际上求出来一组合法解之后调整一下，根据 $p_i - p{i-1}$ 的正负性来判断就 OK，这样构造出的序列就是合法。如果图里有负环就倒闭了。

注意到我们还有 $|p_i - p_{i-1}| = 1$ 这个条件，经过这个条件的约束下，我们去做 SLF 优化的 SPFA，那么实际上复杂度和 01 BFS 等价，是 $O(n+m)$ 的，所以很稳健啊兄弟们（手动 at Qzong）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair

const int N = 5e3 + 10;
int dis[N],cnt[N],n,m;
bool vis[N];
vector <pii> G[N];

bool SPFA(int s) {
    deque <int> q;
    memset(dis,0x3f,sizeof dis);
    dis[s] = 0;++cnt[s];
    q.push_back(s);vis[s] = 1;
    while (!q.empty()) {
        int x = q.front();q.pop_front();
        vis[x] = 0;
        for (auto [y,w] : G[x]) {
            if (dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                cnt[y] = cnt[x] + 1;
                if (!vis[y]) {
                    if (!q.empty() && dis[y] > dis[q.front()]) {
                        q.push_back(y);
                    } else q.push_front(y);
                    if (cnt[y] >= n+1) {
                        return 1;
                    }
                    vis[y] = 1;
                }
            }
        }
    }
    return 0;
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    // for (int i = 0;i <= n;++i) G[n+1].push_back(mp(i,0));
    for (int i = 1;i <= n;++i) G[i-1].push_back(mp(i,1));
    for (int i = 1;i <= n;++i) G[i].push_back(mp(i-1,1));
    bool fa = 0;
    for (int i = 1;i <= m;++i) {
        int x,y,w;cin >> x >> y >> w;
        if (w > (y-x+1)) fa = 1;
        G[y].push_back(mp(x-1,-w));
        G[x-1].push_back(mp(y,w));
    }
    G[0].push_back(mp(1,1));G[1].push_back(mp(0,1));
    G[0].push_back(mp(n,0));G[n].push_back(mp(0,0));
    //p[1]必须是1 p[n]必须是0
    bool ans = SPFA(0);
    // for (int i = 1;i <= n;++i) cerr << dis[i] << " ";
    for (int i = 1;i <= n;++i) {
        if (dis[i] < 0) fa = 1;
    }
    if (ans || fa) {
        cout << "?";
    } else {
        cout << "! ";
        for (int i = 1;i <= n;++i) {
            // assert(dis[i] >= 0);
            if (dis[i] - dis[i-1] > 0) cout << "(";
            else cout << ")";
        }
    }
    return 0;
}

例题4.Rainbow Bracket Sequence

括号序列匹配+最优化问题+一系列限制条件+较小的数据范围=最小费用最大流模型

赛时想到过上下界，但是因为不会这个东西就没继续往下想。

不过其实我们有本质更简单的做法，即先假设所有位置都填了左括号，此时需要选出 nn 个位置将其变为右括号

用经典 trick，合法括号序列的充要条件为：

  • 后 $2i−1$ 个位置中至少要有 $i$ 个右括号；
  • 最后 $2n$ 个位置中恰好要有 $n$ 个右括号；

同时由于我们预设了每个位置都填左括号，则下界的要求初始时一定是满足的（特判掉显然无解的情况后）

此时每个颜色就有了一个将左括号转为右括号数的上界，此时就可以用传统的费用流模型来处理了

将每个颜色拆出一个虚点，并求出每个颜色 $j$ 最多只能转化的右括号个数 $lim_j$

  • $S$ 向 $2n$ 连 $(n,0)$ 的边；
  • 点 $i+1$ 向点 $i$ 连 $(⌊\frac{i}{2}⌋,0)$ 的边；
  • 点 $i$ 向点 $n+c_i$ 连 $(1,v_i)$ 的边；
  • 点 $n+j$ 向 $T$ 连 $(lim_j,0)$ 的边；

最后用 $∑v_i$ 减去该图的最小费用最大流即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
/*
Undo the destiny.
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
    int v = getchar();T f = 1;t = 0;
    while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
    while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
    t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
    read(t);read(args...);
}

const ll mod = 998244353;
const double eps = 1e-10;
const int N = 2e5 + 10;
int cnt,n,tot;
template<class T>
struct MinCostFlow {
    struct _Edge {
        int to;
        T cap;
        T cost;
        _Edge(int to_, T cap_, T cost_) : to(to_), cap(cap_), cost(cost_) {}
    };
    int n;
    vector<_Edge> e;
    vector<vector<int>> g;
    vector<T> h, dis;
    vector<int> pre;
    bool dijkstra(int s, int t) {
        dis.assign(n, numeric_limits<T>::max());
        pre.assign(n, -1);
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> 
que;
        dis[s] = 0;
        que.emplace(0, s);
        while (!que.empty()) {
            T d = que.top().first;
            int u = que.top().second;
            que.pop();
            if (dis[u] != d) {
                continue;
            }
            for (int i : g[u]) {
                int v = e[i].to;
                T cap = e[i].cap;
                T cost = e[i].cost;
                if (cap > 0 && dis[v] > d + h[u] - h[v] + cost) {
                    dis[v] = d + h[u] - h[v] + cost;
                    pre[v] = i;
                    que.emplace(dis[v], v);
                }
            }
        }
        return dis[t] != numeric_limits<T>::max();
    }
    MinCostFlow() {}
    MinCostFlow(int n_) {
        init(n_);
    }
    void init(int n_) {
        n = n_;
        e.clear();
        g.assign(n, {});
    }
    void addEdge(int u, int v, T cap, T cost) {
        g[u].push_back(e.size());
        e.emplace_back(v, cap, cost);
        g[v].push_back(e.size());
        e.emplace_back(u, 0, -cost);
    }
    pair<T, T> flow(int s, int t) {
        T flow = 0;
        T cost = 0;
        h.assign(n, 0);
        while (dijkstra(s, t)) {
            for (int i = 0; i < n; ++i) {
                h[i] += dis[i];
            }
            T aug = numeric_limits<int>::max();
            for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
                aug = min(aug, e[pre[i]].cap);
            }
            for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
                e[pre[i]].cap -= aug;
                e[pre[i] ^ 1].cap += aug;
            }
            flow += aug;
            cost += aug * h[t];
        }
        return make_pair(flow, cost);
    }
    struct Edge {
        int from;
        int to;
        T cap;
        T cost;
        T flow;
    };
    vector<Edge> edges() {
        vector<Edge> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.cost = e[i].cost;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};
MinCostFlow<ll> G;

ll m,l[N],c[N],v[N];
void solve() {
    cin >> n >> m;n *= 2;
    ll sum = 0;
    for (int i = 1;i <= m;++i) cin >> l[i],l[i] = -l[i];
    for (int i = 1;i <= n;++i) cin >> c[i],++l[c[i]];
    for (int i = 1;i <= n;++i) cin >> v[i],sum += v[i];
    G.init(n + m + 10);
    int s = n + m + 1,t = s + 1;
    G.addEdge(s,n,n/2,0);
    for (int i = n;i > 1;--i) G.addEdge(i,i-1,(i-1)/2,0);
    for (int i = 1;i <= n;++i) G.addEdge(i,n + c[i],1,v[i]);
    bool flag = 0;
    for (int i = 1;i <= m;++i) {
        if (l [i] < 0) {
            flag = 1;
            break;
        }
        G.addEdge(n + i,t,l[i],0);
    }
    if (!flag) {
        auto now = G.flow(s,t);
        if (now.first == n / 2) cout << sum - now.second << "\n";
        else cout << "-1\n";
    } else {
        cout << "-1\n";
    }

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin >> T;
    while (T--) solve();
    return 0;
}

括号模型题的简单概括

https://doubeecat.cn/post/括号模型题的简单概括/

作者

Doubeecat

发布于

2025-03-14

更新于

2025-09-18

许可协议

关注我

链接

分类

最新文章

归档

标签

2-SAT1
BFS1
BSGS1
CDQ分治1
CV7
CV , transformer1
CV, 分割1
CV, 多模态1
CV,Transformer1
CV,分割2
CV,机器学习1
DFS序1
DL2
DP20
Dijkstra1
Dirchlet 卷积1
ETT1
Kruskal2
Kruskal 重构树2
LCA1
MST2
NTT1
RMQ1
Tarjan4
Transformer2
bitset1
codeforces1
hash1
nim游戏1
transformer1
二分3
二分图1
二维数点1
位运算2
决策单调性1
凸包1
分块2
分治2
分治NTT1
割点1
区间DP2
单调栈3
博弈论1
图论12
多项式1
字符串1
容斥原理2
差分1
差分约束1
并查集2
思维8
扫描线2
拉格朗日插值1
拓扑排序2
搜索1
数位DP2
数学10
数据结构5
数论5
数论分块1
整体二分1
暴力3
最大流2
最小割2
最小环1
最小费用最大流1
最短路3
杜教筛1
构造3
枚举1
树1
树上问题8
树形DP3
树状数组3
树链剖分2
根号分治2
欧拉函数1
毒瘤1
状压DP1
矩阵1
神经网络1
积性函数1
线性DP3
线性基1
线段树8
线段树分治1
组合数学1
缩点1
网络流2
背包5
莫比乌斯反演1
计数问题2
负环1
贪心1
递归2
闵可夫斯基和1
×