#A. 让人兴奋不已的字符串问题

    Type: Default 1000ms 512MiB

让人兴奋不已的字符串问题

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小 M 给了你 nn 个括号序列 s1,s2,s3,,sns_1,s_2,s_3,\dots,s_n。你的问题是,有多少的有序对 (i,j)(i,j) 满足 i,j[n]i,j\in[n]si,sjs_i,s_j 拼接起来之后是合法括号序列。

一个合法括号序列指:可以在序列中插入 0,+0,+ 两种字符使得这个算式合法。

如:(()()) 是合法的,因为可以变成 0+((0+0)+(0+0))0+((0+0)+(0+0)),而 )()))((()) 是不合法的。

输入格式

本题多测

每个测试点第一个正整数 TT 表示测试点数目。

对每一个测试点,第一行一个正整数 nn

接下来 nn 行,每行一个括号序列表示 sis_i

输出格式

每个测试点一个非负整数表示答案。

测试样例

3
2
(
)
3
()
(())
((()))
3
(()())
((
))
1
9
2
样例输入 样例输出
32()3()(())((()))3(()())(()) 192
见下发 string/string2.in\textit{string/string2.in} 见下发 string/string2.ans\textit{string/string2.ans}
见下发 string/string3.in\textit{string/string3.in} 见下发 string/string3.ans\textit{string/string3.ans}
见下发 string/string4.in\textit{string/string4.in} 见下发 string/string4.ans\textit{string/string4.ans}

样例解释

对于样例 11

  • 测试点 11(1,2)(1,2) 满足。
  • 测试点 22 有 $(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)$ 满足。
  • 测试点 33(1,1),(2,3)(1,1),(2,3) 满足。

样例 22 满足测试点 11 的限制。

样例 33 满足测试点 33 的性质

样例 44 满足测试点 55 的性质。

数据范围

下面 si\sum |s_i| 表示单组数据点中,sis_i 长度的和。

对于所有数据,T10T\leq 10n105n\leq 10^5si2×106\sum |s_i|\leq 2\times10^6

| 测试点编号 | TT\leq | nn\leq | si\sum |s_i|\leq | 特殊性质 | | :--------: | :-----: | :------------: | :--------------: | :---------------------------: | | 11 | 1010 | 10001000 | 30003000 | 无 | | 22 | 1010 | 10510^5 | 2×1062\times 10^6 | 每个 sis_i 的左右括号数目相等 | | 33 | 55 | 2×1032\times 10^3 | 2×1062\times 10^6 | sis_i 随机生成 | | 44 | 1010 | 5×1045\times 10^4 | 10610^6 | 无 | | 55 | 1010 | 10510^5 | 2×1062\times 10^6 | 无 |

时间限制:1s\tt 1s

空间限制:512MB\tt 512MB

Odoo 省选模拟赛

Not Attended
Status
Done
Rule
OI
Problem
3
Start at
2024-2-29 8:00
End at
2024-2-29 12:00
Duration
4 hour(s)
Host
Partic.
4