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

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，这个递推式的含义是考虑从匹配那个点的转移过来。
#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：

#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）

/*
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 减去该图的最小费用最大流即可

/*
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;
}