51 Nod 1791 合法括号子段【分治+字符串】
2024-10-12 20:26:53
基准时间限制:1 秒 空间限制:131072 KB 分值: 40
有一个括号序列,现在要计算一下它有多少非空子段是合法括号序列。
合法括号序列的定义是:
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
分析:
这里,我们需要明确区分一个定义,什么叫做子段?什么叫做子序列?子段是子序列的一种,也叫做连续子序列,而子序列呢?如果不要求连续,则是可以从原序列中任意取,但是要保持原先的先后顺序即可。
一个简单的分治,分别控制子段的左右两端点在左右两个区间内,然后从中间开始查找,控制左右两个半区间的合法性即可。
下面给出AC代码:
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = ;
int dp[maxn];
char s[maxn];
int main (void)
{
ios::sync_with_stdio(false);
int n;
scanf("%d",&n);
for(int k=;k<=n;++k)
{
scanf("%s",s);
stack<int>st;
int len=strlen(s);
for(int i=;i<len;++i)
{
if(s[i]==')')
{
if(st.empty())
continue;
int tmp=st.top();
st.pop();
if(tmp!=)
dp[i]=dp[tmp-]+;
else
dp[i]=;
}
else
st.push(i);
}
ll ans=;
for(int i=;i<len;++i)
{
ans+=dp[i];
dp[i]=;
}
printf("%lld\n",ans);
}
return ;
}
最新文章
- 搭建FTP服务器
- PLSQL Developer注册码
- SharePoint 2010 文档管理之过期归档工具
- Qt: 界面中使用中文(三种方法,QApplication::translate可指定编码)
- 【项目经验】如何用TexturePacker &; Physicseditor开发游戏
- opencv里面CV_32FC1家族
- Codevs 1001 舒适的路线 2006年 NOIP全国联赛提高组
- 网络协议- HTTP
- box flex 弹性盒模型(转载)
- 2016_ThinkinG of everyDay
- crtmpserver初探
- Codeforces 768B Code For 1
- oracle 判断字段内是否含中文
- python3 生成器和生成器表达式
- 前端JS常见面试题(代码自撸)
- effective java——12考虑实现coparable接口
- mysql状态分析之show global status(转)
- java 多线程并发 synchronized 同步机制及方式
- 013-并发编程-java.util.concurrent.locks之-AbstractQueuedSynchronizer-用于构建锁和同步容器的框架、独占锁与共享锁的获取与释放
- 服务器返回的json数据中含有null的处理方法
热门文章
- UITextFiled的输入框改成一条下划线
- 免费SSL&;付费SSL证书,该如何选择?
- Java 银行家算法
- React Native出现";Native module cannot be null";问题
- 优化设计提高sql类数据库的性能
- JMeter 插件 Json Path 解析HTTP响应JSON数据
- 如何配置FTP服务器,方便操作服务器文件
- 基于阿里云的JavaEE系统框架介绍
- vue-router源码学习(一)
- SQLServer Agent执行[分发清除: distribution] 无法删除快照文件