Bracket Sequences Concatenation Problem括号序列拼接问题(栈+map+思维)
A bracket(括号) sequence is a string containing only characters "(" and ")".A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, bracket sequences "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.
You are given n bracket sequences s1,s2,…,sn. Calculate the number of pairs i,j(1≤i,j≤n) such that the bracket sequence si+sj is a regular bracket sequence. Operation + means concatenation i.e. "()(" + ")()" = "()()()".
If si+sj and sj+si are regular bracket sequences and i≠j, then both pairs (i,j) and (j,i) must be counted in the answer. Also, if si+si is a regular bracket sequence, the pair (i,i) must be counted in the answer.
Input
The first line contains one integer n(1≤n≤3⋅105)— the number of bracket sequences. The following n lines contain bracket sequences — non-empty strings consisting only of characters "(" and ")". The sum of lengths of all bracket sequences does not exceed 3⋅105
.
Output
In the single line print a single integer — the number of pairs i,j(1≤i,j≤n)
such that the bracket sequence si+sj
is a regular bracket sequence.
Examples
Input
3
)
()
(
Output
2
Input
2
()
()
Output
4
Note
In the first example, suitable pairs are (3,1)and (2,2)
.
In the second example, any pair is suitable, namely (1,1),(1,2),(2,1),(2,2)
.
题目意思:有n个字符串,每个字符串都只有'('和')'组成,从中找出两个字符串si,sj( i ! = j)可以构成完全匹配的个数,同样如果si自身也能完全匹配也要算进去。
解题思路:所有的字符串可以分为3类:
1: 自身完美匹配型(即左括号和右括号完美匹配)
2:除去完全匹配的子串,剩下的都是左括号。
3:除去完全匹配的子串,剩下的都是右括号。
对于第一类他的个数ans=c(n,2)*A(2,2)+n(它自身构成的完美匹配),对于第二类和第3类,用map查询一遍(如果有左括号的个数等于右括号的个数,ans=(左括号的种类*右括号的种类),最后不要忘记除去2,因为我们算了两遍。
#include<cstdio>
#include<cstring>
#include<map>
#include<stack>
#include<algorithm>
#define ll long long int
#define MAX 300010
using namespace std;
map<ll,ll>mp;
char str[MAX];
int main()
{
ll i,n,len,m,k;
ll counts,ans,sum;
scanf("%lld",&n);
getchar();
m=;
ans=;
while(n--)
{
stack<char>s;
scanf("%s",str);
len=strlen(str);
for(i=; i<len; i++)
{
if(!s.empty())
{
if(s.top()=='('&&str[i]==')')
{
s.pop();
}
else
{
s.push(str[i]);
}
}
else
{
s.push(str[i]);
}
}
if(s.empty())///自身完全匹配
{
m++;
}
else
{
counts=s.size();
sum=;
while(!s.empty())
{
if(s.top()=='(')
{
sum++;///记录左括号个数
}
s.pop();
}
if(sum==)///剩下的都是右括号
{
mp[-counts]++;///负数代表右括号
}
else if(sum==counts)///栈里剩下的都是左括号
{
mp[counts]++;///正数代表左括号
}
}
}
map<ll,ll>::iterator it;
for(it=mp.begin(); it!=mp.end(); it++)
{
k=it->first;
if(mp.count(-k))///只有存在左括号数等于右括号数的才存在完美匹配
{
ans+=(ll)(it->second)*mp[-k];
}
}
printf("%lld\n",ans/+m*m);
return ;
}
最新文章
- 十分钟使用github pages +hexo拥有个人博客
- 细数Javascript技术栈中的四种依赖注入
- Mean Shift Tracking: 2000-2012回顾 (新论文更新)
- linux安装SVN
- AngularJs的UI组件ui-Bootstrap分享(三)——Accordion
- 数据和C
- sql语句用&#39;in&#39;执行多条语句时候,执行错误的解决方法
- System.arraycopy--findbugs检查引发的更改
- Algorithm 算法
- MOS管常识
- Linux 基础(3)
- learning makefile ?=
- 用贝叶斯定理解决三门问题并用Python进行模拟(Bayes&#39; Rule Monty Hall Problem Simulation Python)
- MySQL技术内幕读书笔记(六)——索引与算法之全文索引
- OpenCV——LBP(Local Binary Patterns)特征检测
- 上云利器,K8S应用编排设计器之快到极致
- [Luogu P1120]小木棍&#183;加强版
- 小马哥课堂-统计学-z分数
- 【BZOJ1951】[Sdoi2010]古代猪文 Lucas定理+CRT
- python进制转换(二进制、十进制和十六进制)及注意事项