上海计算机学会2022年8月月赛C++丙组T5括号计分_平衡括号(一) 内存限制: 256 mb时间限制: 1000 ms 本题已有精讲视频可供观看 点击

括号计分

内存限制: 256 Mb时间限制: 1000 ms

题目描述

括号序列是由 ( 与 ) 构成的序列。平衡的括号序列要求 ( 与 ) 出现次数一样多，而且序列的每个前缀里 ( 出现次数不低于 ) 的出现次数。

对平衡的括号序列，定义一种计分规则如下：

• 如果只有一对括号 ()，只算 1 分；
• (A) 的分数是 A 的 2 倍；
• AB 的分数是 A 与 B 的和，其中 A 与 B 必须是平衡的括号序列。

给定一个平衡的括号序列，请计算它的分数，由于数字可能很大，输出答案模 1,000,000,007 的余数。

输入格式

单个字符串：表示输入的序列。

输出格式

单个整数：表示括号序列的分数模 1,000,000,007 的余数。

数据范围

设 n 表示输入字符串的长度，

• 对于 50% 的数据，1≤n≤200；
• 对于 100% 的数据，1≤n≤200,000。

样例数据

 输入:
()()()
输出:
3

输入:
((()))
输出:
4

解析：

因为数值跟深度有关，我们可以遇到左括号就增加深度，遇到右括号就计算数值。

根据深度和括号里的数值来求。

详见代码： 

#include <bits/stdc++.h>
using namespace std;
string a;
long long  b[1000005];
int main() {
    int len;
    int lever = 0;//括号级别
    cin >> a;
    len = a.length();
    for (int i = 0; i < len; i++) {
        if (a[i] == '(') {//左括号
            lever++;//级别加1
        } else {//右括号
            if (b[lever] == 0) {//分数为0（里边没有括号）
                b[lever]++;//加一
            } else {//不为0（里边有括号）
                b[lever] *= 2;//分数乘2
            }
            b[lever-1] += b[lever];//分数累加到上一个级别
            b[lever] = 0;//当前级别分数归零
            lever--;//级别减一
            b[lever] %= 1000000007;//分数求模
        }
    }
    cout << b[0] << endl;
}

 上海市西南模范中学 房和田老师的递归算法：

计算分数是一个递归的过程
从第一个开始循环，如果当前是 "(" ，那就 dfs 找到和它配对的 ")" 顺便算一下这里面的分数再乘2就可以
然后我们发现输入的括号序列会有很多个 "()"，（这里指的是在外层的）
把他们的分数都用 dfs 算出来然后加在一起就可以了，在 "()" 里面的多个并列的 "()" 也是这样，都算出来，再加到一起就可以了
代码非常的简单：

#include <cstring>
#include <iostream>
using namespace std;
const int mod = 1000000007;
int len,ans;
int loc,idx = 0;
string c;
int dfs(int idx) {
	int score = 0,cnt = 0;
	for(int i = idx; i < len; i ++) {
		if(c[i] == '(') {
			if(i != idx && c[i - 1] == ')')
			{
				score = (score + dfs(i)) % mod;
				i = loc;
			}
			else cnt ++;
		} else {
			cnt --;
			if(i != 0 && c[i - 1] == ')') score = score * 2 % mod;
			else score = 1;
		}
		if(cnt == 0) {
			loc = i;
			return score % mod;
		}
	}
}
int main() {
	cin >> c;
	len = c.size();
	while(idx != len) {
		ans = (ans + dfs(idx)) % mod;
		idx = loc + 1;
	}
	cout << ans << endl;
	return 0;
}