【51nod 1791】 合法括号子段
2024-09-30 12:20:38
有一个括号序列,现在要计算一下它有多少非空子段是合法括号序列。
合法括号序列的定义是:
1.空序列是合法括号序列。
2.如果S是合法括号序列,那么(S)是合法括号序列。
3.如果A和B都是合法括号序列,那么AB是合法括号序列。
Input
多组测试数据。
第一行有一个整数T(1<=T<=1100000),表示测试数据的数量。
接下来T行,每一行都有一个括号序列,是一个由'('和')'组成的非空串。
所有输入的括号序列的总长度不超过1100000。
Output
输出T行,每一行对应一个测试数据的答案。
Input示例
5
(
()
()()
(()
(())
Output示例
20
1
3
1
2
题解
对于判断括号序列的合法性,有一种很简洁的方法:
设左括号为-1,右括号为+1,求得一个前缀和数组\(f\)。
那么正确的括号序列必然是以-1开头,0结尾,且中间的数都小于等于零。
知道了这个,此题还需要链表+RMQ操作
首先对于每一个前缀建一个链表\(nxt[f[i]]\)。
假设我们以i为括号序列起点,那么它右边的前缀都得\(-f[i-1]\),那么下一个为0的位置是\(nex[f[i-1]]\),我们已经预处理它的位置
直接RMQ查询即可。诶,这样好像也会超时,最坏情况下也是\(O(n^2)\)的,因为我们会沿着链表跳很多次。。。
那么就倒着做吧,我们记录好以nex[i]为结尾的的答案,以后直接累加即可,至此,时间复杂度降为\(O(nlogn)\)
参考代码
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 1000000000
#define PI acos(-1)
#define REP(i,x,n) for(ll i=x;i<=n;i++)
#define DEP(i,n,x) for(ll i=n;i>=x;i--)
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void Out(ll a){
if(a<0) putchar('-'),a=-a;
if(a>=10) Out(a/10);
putchar(a%10+'0');
}
const int N=1100000+10;
char a[N];
int f[N];
map<int,int> fa;
map<int,int>vis;
int nxt[N];
int dp[N][20];
void RMQ_init(int n){
for(int i=1;i<=n;i++) dp[i][0]=f[i];
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
}
int RMQ(int L,int R){
int k=0;
while((1<<(k+1))<=R-L+1) k++;
return max(dp[L][k],dp[R-(1<<k)+1][k]);
}
int main() {
int T=read();
while(T--){
scanf("%s",a+1);
f[0]=0;int n=strlen(a+1);
for(int i=1;i<=n;i++){
if(a[i]=='(') f[i]=f[i-1]-1;
else f[i]=f[i-1]+1;
}
fa.clear();vis.clear();RMQ_init(n);
ll ans=0;
for(int i=n;i>=0;i--){
if(!fa[f[i]]) fa[f[i]]=-1;
nxt[i]=fa[f[i]];
fa[f[i]]=i;
}
vis[-1]=0;
for(int i=n;i>=1;i--){
if(a[i]=='('){
if(nxt[i-1]==-1) vis[i-1]=0;
else{
if(RMQ(i,nxt[i-1])<=f[i-1]) vis[i-1]+=vis[nxt[i-1]]+1;
else vis[i-1]=0;
}
ans+=vis[i-1];
}
}
printf("%lld\n",ans);
}
return 0;
}
最新文章
- 扩展Exception,增加判断Exception是否为SQL引用约束异常方法!
- Oracle中把一个DateTime的字符串转化成date类型。to_date(&#39;2016/12/8 18:55:43&#39;,&#39;yyyy/MM/dd hh24:mi:ss&#39;),
- java反射详解(转)
- oracle的安装与plsql的环境配置
- 面向对象涉及SOLID原则
- 引用jquery框架后出错
- 基于Tire树和最大概率法的中文分词功能的Java实现
- 【百度地图API】暑假放假回老家——城市切换功能
- Android 使用AsyncTask 下载图片的例子,学会使用AsyncTask
- IOS常见的加密方法,常用的MD5和Base64
- 8000个JQuery特效(插件)
- QT4.8应用控制程序设计
- mysql中gbk_chinese_ci与gbk_bin区别
- 【BZOJ3669】【NOI2014】魔法森林 LCT
- struct/class等内存字节对齐问题详解
- Redis未授权漏洞利用方式
- SPOJ QTREE5 lct
- Python day16 tag式整体退出技巧
- Android -- service 服务的创建与使用,生命周期,电话监控器
- 定时任务crond服务