51 Nod 1791 合法括号子段【分治+字符串】

1791 合法括号子段

基准时间限制:1 秒 空间限制:131072 KB 分值: 40

难度:4级算法题

有一个括号序列,现在要计算一下它有多少非空子段是合法括号序列。

合法括号序列的定义是:

1.空序列是合法括号序列。

2.如果S是合法括号序列,那么(S)是合法括号序列。 3.如果A和B都是合法括号序列,那么AB是合法括号序列。

Input

多组测试数据。
第一行有一个整数T(1<=T<=1100000),表示测试数据的数量。
接下来T行,每一行都有一个括号序列,是一个由'('和')'组成的非空串。
所有输入的括号序列的总长度不超过1100000。

Output

输出T行,每一行对应一个测试数据的答案。

Input示例

5
(
()
()()
(()
(())

Output示例

0
1
3
1
2

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1791

分析:

这里,我们需要明确区分一个定义,什么叫做子段?什么叫做子序列?子段是子序列的一种,也叫做连续子序列,而子序列呢?如果不要求连续,则是可以从原序列中任意取,但是要保持原先的先后顺序即可。

一个简单的分治,分别控制子段的左右两端点在左右两个区间内,然后从中间开始查找,控制左右两个半区间的合法性即可。

下面给出AC代码:

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <string>
 5 #include <algorithm>
 6 #include <stack>
 7 using namespace std;
 8 typedef long long ll;
 9 const int maxn = 1100005;
10 int dp[maxn];
11 char s[maxn];
12 int main (void)
13 {
14     ios::sync_with_stdio(false);
15     int n;
16     scanf("%d",&n);
17     for(int k=1;k<=n;++k)
18     {
19         scanf("%s",s);
20         stack<int>st;
21         int len=strlen(s);
22         for(int i=0;i<len;++i)
23         {
24             if(s[i]==')')
25             {
26                 if(st.empty())
27                     continue;
28                 int tmp=st.top();
29                 st.pop();
30                 if(tmp!=0)
31                     dp[i]=dp[tmp-1]+1;
32                 else
33                     dp[i]=1;
34             }
35             else
36                 st.push(i);
37         }
38         ll ans=0;
39         for(int i=0;i<len;++i)
40         {
41             ans+=dp[i];
42             dp[i]=0;
43         }
44         printf("%lld\n",ans);
45     }
46     return 0;
47 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P3809 【模版】后缀排序

题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

26980
来自专栏漫漫深度学习路

pytorch学习笔记(十七):python 端扩展 pytorch

pytorch 虽然提供了很多的 op 使得我们很容易的使用。但是当已有的 op 无法满足我们的要求的时候,那就需要自己动手来扩展。 pytorch 提供了两种...

31070
来自专栏小樱的经验随笔

UVA 11636-Hello World!(水题,猜结论) UVA11636-Hello World!

UVA11636-Hello World! Time limit: 1.000 seconds When you first made the computer ...

37440
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

17010
来自专栏Python小屋

Python版堆排序算法

其他排序算法的Python实现请参考:Python版归并排序算法(附Python程序__name__属性用法演示视频),侏儒排序算法原理与Python实现,Py...

35650
来自专栏GreenLeaves

Oracle dbms_random随机函数包

dbms_random是oracle提供的一个随机函数包,以下是它的一些常用的功能: 1、dbms_random.value 作用:生成一个大于等于0,大于等于...

21850
来自专栏轮子工厂

一口气吃下数组的存储方式

Long long ago,我们讲到了数组《聊一聊数组背后的那点事》,这个已经是迈进指针的第一步了,主要的内容是一维数组,今天我们将讲述二维数组。当结束了今天的...

19410
来自专栏owent

最长单调子序列 复杂度nlog(n)

7910
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

30790
来自专栏书山有路勤为径

包含min函数的栈

LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入...

10710

扫码关注云+社区

领取腾讯云代金券