ACM思维题训练集合 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). 模拟稍微有一下就可以了
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
template <typename t>
void read(t &x)
{
char ch = getchar();
x = 0;
t f = 1;
while (ch < '0' || ch > '9')
f = (ch == '-' ? -1 : f), ch = getchar();
while (ch >= '0' && ch <= '9')
x = x * 10 ch - '0', ch = getchar();
x *= f;
}
#define wi(n) printf("%d ", n)
#define wl(n) printf("%lld ", n)
#define rep(m, n, i) for (int i = m; i < n; i)
#define rrep(m, n, i) for (int i = m; i > n; --i)
#define P puts(" ")
typedef long long ll;
#define MOD 1000000007
#define mp(a, b) make_pair(a, b)
#define N 1005
#define fil(a, n) rep(0, n, i) read(a[i])
//---------------https://lunatic.blog.csdn.net/-------------------//
map<LL, LL> mp;
char con[N];
int main()
{
LL i, p, j, n, check;
LL cont = 0, ans = 0, len1, len2;
scanf("%lld", &n);
getchar();
for (j = 1; j <= n; j )
{
p = check = 0;
len1 = len2 = 0;
memset(con, 0, sizeof(0));
scanf("%s", con);
for (i = 0; i < 300009; i )
{
if (con[i] == 0)
break;
if (con[i] == '(')
{
len1 ;
p ;
}
else
{
p--;
if (len1)
len1--;
else
len2 ;
}
}
if (len1 == 0 && len2 == 0)
cont ;
else
{
if (len1 == 0)
mp[p] ;
if (len2 == 0)
mp[p] ;
}
}
ans = cont * cont;
map<LL, LL>::iterator it1;
for (it1 = mp.begin(); it1 != mp.end(); it1 )
{
if (it1->first > 0)
break;
if (mp[-(it1->first)] > 0)
ans = (it1->second) * mp[-(it1->first)];
}
printf("%lldn", ans);
return 0;
}
