C/C++教程

CF1625 E1. Cats on the Upgrade (easy version)题解

本文主要是介绍CF1625 E1. Cats on the Upgrade (easy version)题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

E1. Cats on the Upgrade (easy version)

题意

给定一个长度为\(n\)的括号串,\(q\)次询问,问区间\([l,r]\)所表示的子串中有多少个合法的括号子串,保证区间\([l,r]\)所表示的子串是合法括号子串。

分析

认为空串也算作广义的括号串。记广义括号串为RBS,则所有的括号串(不含空串)都有形如(RBS)(RBS)...(RBS)的形式。不妨设计状态dp[i],表示以第\(i\)个字符为结尾,连续的(RBS)的个数,特殊地,dp[0] = 0。那么对于所有前缀这个问题就已经解决了,只需要一个前缀和就可以多次询问,于是可以定义sum[i] = dp[1] + dp[2] + ... + dp[i],特殊地,sum[0] = 0

若询问的是区间\([l,r]\),sum[r] - sum[l-1]计算了以区间\([l,r]\)中的所有点为结尾的贡献,显然这样计算很可能会多算。由于题目保证区间\([l,r]\)所表示的子串是合法括号子串,对于\([l,r]\)中的每一个点\(i\)来说,只有当第\(i\)个字符是右括号,且以其为结尾的连续的(RBS)中能够包含第\(l\)个字符(其一定是左括号),才会多算,且对于每个满足上述条件的点来说一定会多算dp[l-1]的贡献。所以就需要计算\([l,r]\)中有多少个满足上述条件的点,由于题目保证区间\([l,r]\)所表示的子串是合法括号子串,显然以\(r\)为结尾的连续(RBS)一定包含了所有满足条件的右括号,且一定不包含\([l,r]\)中不满足条件的右括号,一个(RBS)严格对应了一个满足条件的右括号,所以\([l,r]\)中有dp[r] - dp[l-1]个满足条件的右括号。

故而最终结果就是sum[r] - sum[l-1] - dp[l-1] * (dp[r] - dp[l-1])

代码

#include <cstdio>
const int maxn = 3e5 + 10;
typedef long long Lint;
int n, q, st[maxn];
Lint dp[maxn], sum[maxn];
int tot;
char s[maxn];
int main() {
    scanf("%d%d", &n, &q);
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') {
            st[tot++] = i;
        } else if (tot) {
            dp[i] = dp[st[tot - 1] - 1] + 1;
            --tot;
        }
        sum[i] = dp[i] + sum[i - 1];
    }
    while (q--) {
        int l, r;
        scanf("%*d%d%d", &l, &r);
        printf("%lld\n", sum[r] - sum[l - 1] - dp[l - 1] * (dp[r] - dp[l - 1]));
    }
    return 0;
}
这篇关于CF1625 E1. Cats on the Upgrade (easy version)题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!