括号序列问题

life_is_movie · 2024-03-22 00:35:54 · 个人记录

判断是否合法

判断 s 是否为合法括号序列的经典方法是贪心思想。该算法同样适用于变种括号序列。

我们维护一个栈，对于 i=1,2,\ldots,|s| 依次考虑：

如果 s_i 是右括号且栈非空且栈顶元素是 s_i 对应的左括号，就弹出栈顶元素。若不满足上述条件，则将 s_i 压入栈中。在遍历整个 s 后，若栈是空的，那么 s 就是合法括号序列，否则就不是。时间复杂度 O(n)。

例题

for (auto x : s)
{
    if (x != '(' && x != ')') continue;
    if (x == '(') stk[++top] = x;
    if (x == ')')
    {
        if (top) top--;
        else
        {
            cout << "NO\n";
            return 0;
        }
    }
}
if (top) cout << "NO\n";
else cout << "YES\n";

合法括号序列计数

合法的括号序列必须满足2个条件。

左括号数量等于右括号
对于任意的前缀，左括号数量大于等于右括号。

所以合法括号序列是一个卡特兰数。

求一个括号序列的合法子串个数

考虑 dp 求解，状态设计 dp_i 为以 i 结尾的合法括号序列个数。

那么答案就是 \sum_{i=1}^n dp_i

状态转移：

使用栈对于每一个左括号开始记录它的位置，当遇到一个右括号，它可以由和自己匹配的位置减去 1 的位置转移而来，即

dp[i]=dp[stk[top--] - 1] + 1

if (s[i] == '(') stk[++top] = i;
else if (top)
{
    dp[i] = dp[stk[top--] - 1] + 1;
}
ans += dp[i];

树上括号序列合法子串个数

例题：csp-s2019T2

考虑给定一个括号序列的时候怎么求合法的括号子串的个数。

借助一个栈做 DP 即可，遇到左括号入栈，遇到右括号尝试匹配。可以证明在括号序列中，每个右括号唯一对应的一个左括号即栈顶的左括号就适合自己去匹配的。

设 f_i 为前 i 个元素的合法括号字串，答案即为 f_n

状态转移：分为选择第 i 个字符或不选第 i 个字符。

若不选第 i 个右括号，则转移到 f_{i-1}
若选择第 i 个右括号，那么就要和此时栈顶的左括号配对构成一对，设栈顶的位置为 j ，则选择后需要转移到 f_{j-1}-f_{j-2}+1 首先加 1 不必多说因为多了一对括号的贡献，为何是 f_{j-1}-f_{j-2} 这个实际是在求以 j-1 结尾的合法括号子串的个数，因为我们选择了 j,i 这段括号如若转移到之前必须保证连续，如果直接转移到 f_{j-1} 这会把不连续的也计算进去，因为我们的状态设计是前 i 个字符而不是以 i 结尾。

那么我们将这样的问题引入到树上，我们在每次 DFS 的同时记录此时的括号情况，如果回溯我们就弹栈即可。对于从根节点出发到某个点的路径来说其实就是一个序列。

设 f_u 为从根到 u 的合法括号子串个数。若当前节点是右括号，如果不选转移到自己的父亲 f_{p_u}。若选择类似于序列上的转移，这一对括号是和栈顶那个节点匹配的，我们需要转移到栈顶那个节点的父亲减去他的父亲的节点就得到了以栈顶父亲结尾的合法括号子串个数再加 1

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 5;
ll n, f[N];
string s;
int fa[N];
vector<int> e[N];
int stk[N], top;
void dfs(int u)
{
    if (s[u] == '(')
    {
        stk[++top] = u;
        f[u] = f[fa[u]];
        for (auto v : e[u]) dfs(v);
        top--;
    }
    else
    {
        if (!top)
        {
            f[u] = f[fa[u]];
            for (auto v : e[u]) dfs(v);
        }
        else
        {
            int t = stk[top--];
            // f[fa[u]] 为不选，f[fa[t]] 为栈顶的父亲，f[fa[fa[t]]] 为栈顶的父亲的父亲
            f[u] = f[fa[u]] + f[fa[t]] - f[fa[fa[t]]] + 1;
            for (auto v : e[u]) dfs(v);
            stk[++top] = t;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s;
    s = " " + s;
    for (int i = 2; i <= n; i++)
    {
        cin >> fa[i];
        e[fa[i]].emplace_back(i);
    }
    dfs(1);
    ll res = 0;
    for (int i = 1; i <= n; i++) res ^= i * f[i];
    cout << res;
    return 0;
}

P10115 [LMXOI Round 1] Placer

定义 f_{i} 为前 i 个字符划分后的最大价值。答案则为 f_n

转移自然是枚举上一个位置 j，且 j+1\sim i 是一个合法的括号序列。

那么 f_{i} = \max(f_i, f_{j} + a_i-a_{j-1})

这么转移的时间复杂度为 O(n^2)

考虑如何优化转移。

记 lst_i 为和 i 这个右括号匹配的左括号的位置，根据括号序列的性质。

当 A 是合法的括号序列，B 是合法的括号序列，此时 AB 也是合法的括号序列。

因此 f_i=\max(f_{lst_i-1}+a_i-a_{lst_i},f_{lst_{lst_{i}-1}-1}+a_i-a_{lst_{lst_i-1}},\cdots)

我们需要在这些状态中找到 \max，可以维护这些状态的前缀 \max，因为它们都是加了固定的数字 a_i。

我们使用一个数组 g 来维护转移的 \max

则 g_i=\max(f_{lst_i-1}-a_{lst_i},g_{lst_i-1})

那么 f_i=\max(f_i-1,g_i+a_i)

注意若 s_i 是左括号，则 f_i 继承前面的答案 f_{i-1} 即可。

#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = j; i <= k; i++)
#define per(i, j, k) for (int i = j; i >= k; i--)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 3e6 + 5, mod = 998244353;
int n, a[N], stk[N], top, lst[N];
ll f[N], g[N];
string s;
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> s;
    s = " " + s;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n)
    {
        if (s[i] == '(') stk[++top] = i;
        else if (top) lst[i] = stk[top--];
    }
    memset(f, 0xc0, sizeof(f));
    memset(g, 0xc0, sizeof(g));
    f[0] = 0;
    rep(i, 1, n)
    {
        f[i] = f[i - 1];
        if (lst[i])
        {
            g[i] = max(f[lst[i] - 1] - a[lst[i]], g[lst[i] - 1]);
            f[i] = max(f[i], g[i] + a[i]);
        }
    }
    cout << f[n];
    return 0;
}

[蓝桥杯 2021 省 AB] 括号序列

合法的括号序列满足如下条件：

左括号数量等于右括号数量
任意前缀左括号个数大于等于有括号的前缀。

本题需要我们求多少种本质不同的添加结果，首先如果添加一对括号是没有意义的，因此我们可以将添加左右括号分别来处理。

例如求解添加左括号的方案，我们可以采取如下方法：

以原字符串的每个右括号为一个结尾，这样可以将字符串分成若干段，对每一段内去考虑添加多少个左括号，如此可以打达到本质不同。

定义 f_{i,j} 为前 i 个位置左括号比右括号多 j 个的方案数。

若 s[i] = '('，此时 f_{i,j}=f_{i-1,j-1}
若 s[i] = ')'，此时我们就在这个段内添加左括号。由于目前左比右多 j 个，因此可以添加的数量为 0\sim j 个。

若我们添加了 0 个左，由于添加了个 0 个左以后，左比右多 j 个，那么在前 i-1 个位置，左应该比右多 j+1 个，即转移到 f_{i-1,j+1}

\cdots

若我们添加了 j+1 个左，由于添加了个 j+1 个左以后，左比右多 j 个，那么在前 i-1 个位置，左应该比右多 0 个，即转移到 f_{i-1,0}

即 f_{i,j}=\sum_{k=0}^{j+1} f_{i-1,k}

由于 f_{i,j-1}=\sum_{k=0}^j f_{i-1,k}

所以 f_{i,j}=f_{i-1,j+1}+f_{i,j-1}

这是添加左括号的情况，那么添加右括号同理，以每一个左括号作为结尾，分成若干段，在这个段内填右括号。

我们可以将原字符串翻转，翻转以后左右对调来处理。

在一个段内即填左又填右，会产生新的贡献吗？

答案是不会的，因为如果在一个段内填写了匹配的括号，去掉它是一样的，所以段内的方案是确定的。

由于要填写最少的括号变得合法，那么答案就是枚举 i，若 f_{n,i} 不为 0 则左比右多 i 个的方案就合法了。

#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = j; i <= k; i++)
#define per(i, j, k) for (int i = j; i >= k; i--)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long, long>;
using a3 = array<int, 3>;
const int N = 5e3 + 5, mod = 1e9 + 7;
string s;
ll n, f[N][N];
ll solve()
{
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '(')
        {
            for (int j = 1; j <= n; j++) f[i][j] = f[i - 1][j - 1];
        }
        else
        {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
            for (int j = 1; j<= n; j++) f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
        }
    }
    for (int i = 0; i <= n; i++) if (f[n][i]) return f[n][i];
    return 0;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> s;
    n = s.size();
    s = " " + s;
    ll l = solve();
    reverse(s.begin() + 1, s.end());
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == ')') s[i] = '(';
        else s[i] = ')';
    }
    ll r = solve();
    cout << (l * r) % mod;
    return 0;
}