#D. [CZOJ 一周一测 R8 D] 不正则表达式

    传统题 1000ms 256MiB

[CZOJ 一周一测 R8 D] 不正则表达式

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.

题目背景

[a-z][a-z][a-z]?[a-z]?qwq

题目描述

定义『合法括号序列』:

  • 空串是合法括号序列。
  • A\tt A 是合法括号序列,则 (A)\texttt{(A)} 是合法括号序列。
  • A,B\tt A, B 均为合法括号序列,则 AB\texttt{AB} 是合法括号序列。

定义『半合法括号序列』包含 (,),*\texttt (, \texttt ), \texttt * 三种字符,其中把每个 *\texttt * 替换为 (\texttt ()\texttt ) 或空字符串中的一种后,存在至少一种方案使该字符串成为合法括号序列。

给出仅包含 (,),*\texttt (, \texttt ), \texttt * 三种字符的字符串 SS,求 SS 的半合法括号序列子串数量。

输入格式

第一行一个正整数 nn 表示 SS 的长度。

第二行一个字符串表示 SS

输出格式

一行一个整数表示答案。

样例

7
(*)*(*)
17

数据规模与约定

测试点编号 nn \leq 特殊性质
11 1616
22 300300
353 \sim 5 50005000
66 2×1052\times 10^5 A
77 B
8108 \sim 10
  • 特殊性质 A:保证 SS 内不含有字符 *\texttt *
  • 特殊性质 B:SS 的每个字符均匀随机生成。

对于 100%100\% 的数据,保证 1n2×1051 \leq n \leq 2\times 10^5

[CZR-008] CZOJ Weekly Exercise Round 8

未参加
状态
已结束
规则
IOI
题目
6
开始于
2024-2-17 17:00
结束于
2024-2-17 22:00
持续时间
5 小时
主持人
参赛人数
20