个人网站用凡科建站好吗,最新网页版传奇,上海市重点企业名单,最新国际军事动态题目描述 一个由小括号组成的字符串可以被称为一个括号序列。但一个括号序列可能并不满足括号匹配的要求。因此#xff0c;我们可以进一步将满足括号匹配的括号序列成为“标准的括号序列。例如字符串)((())是一个括号序列但不是标准的括号序列#xff0c;而字符串…题目描述 一个由小括号组成的字符串可以被称为一个括号序列。但一个括号序列可能并不满足括号匹配的要求。因此我们可以进一步将满足括号匹配的括号序列成为“标准的括号序列。例如字符串)((())是一个括号序列但不是标准的括号序列而字符串()(())是一个标准的括号序列。给定一个括号序列你需要对求出这个括号序列的所有不同的子串中有多少个是标准的括号序列一个括号序列的子串指的是这个序列从某个位置起始、到某个位置截止的子字符串。如果两个子串拥有不同的起始位置或截止位置那么它们就被认为是括号序列的不同的子串。 输入 包括一行一个字符串为给定的括号序列。 输出 输出一个整数为标准的括号序列的子串的个数。 样例输入 ()(())样例输出 4提示 设输入字符串的长度为n。对于30%的数据满足n≤200。对于60%的数据满足n≤5000。对于100%的数据满足1≤n≤10^6。 题解题目要求必须是子串也就是要连续的因此当前面有一个合法的话如果紧接着又出现了一个合法的那么方法数就是11种如果前面有n种连续的合法的括号的话紧接着又出现一个合法的那么方法数就是1n所以每当遇到一个合法的括号对的时候看他前面是否有连续的括号对用stack记录用stack.pre来记录当以这个括号作为两个连续合法序列的分隔时这个括号后面有多少个合法的序列。 #include bits/stdc.h
#define ll long long
#define met(a,x) memset(a,x,sizeof(a))
#define inf 0x3f3f3f3f
using namespace std;
const int N1e610;
const int mod1e97;
char a[N];
struct node
{int x,pre;
} b;
stacknode s;
int main()
{ios::sync_with_stdio(false);cin.tie(0);cina1;int lenstrlen(a1);ll ans0;ll sum0;for(int i1; ilen; i){if(a[i]()b.x1;elseb.x2;if(!s.empty()){if(s.top().x1b.x2){s.pop();if(s.empty()){ans(sum1);sum;}else{ans(s.top().pre1);s.top().pre;}}elses.push(b);}elses.push(b);}coutansendl;return 0;
} 转载于:https://www.cnblogs.com/nublity/p/10278933.html
