题意

Candela是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。这一天，刚刚起床的Candela画了一排括号序列，其中包含小括号( )、中括号[ ]和大括号{ }，总长度为N。这排随意绘制的括号序列显得杂乱无章，于是Candela定义了什么样的括号序列是美观的：

空的括号序列是美观的；
若括号序列A是美观的，则括号序列 (A)、[A]、{A} 也是美观的；
若括号序列A、B都是美观的，则括号序列AB也是美观的。

例如 (){} 是美观的括号序列，而 )({)[}]( 则不是。

现在Candela想在她绘制的括号序列中，找出其中连续的一段，满足这段子序列是美观的，并且长度尽量大。你能帮帮她吗？

字符串长度不超过100000

分析

参照zylAK的题解。

做法：
括号匹配就用栈来模拟：（具体步骤如下）

遇到左括号就入栈。
遇到右括号：
a.如果和栈顶（左）括号匹配，则出栈，同时匹配长度+2.（因为如果最近的都不匹配，那么往后的中间一定会夹杂这个未匹配的右括号，这是不符合完美匹配的）
b.如果不匹配栈顶括号，那么清空栈并且配备长度重置为0.
在入出栈的过程中记录最长匹配。
输出最长匹配。

第一步入栈可以找到字符串中第一个左括号入栈，不过数据点不影响

时间复杂度\(O(len)\)

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;
    rg char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x){
    return x=read<T>();
}
typedef long long ll;

char seq[100001];
int stk[100001],top;
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  printf("%d %d %d %d %d %d",'(',')','[',']','{','}');
    scanf("%s",seq);
    int n=strlen(seq),ans=0,len=0;
    stk[++top]=seq[0];
    for(int i=1;i<n;++i){
        if(seq[i]==stk[top]+1||seq[i]==stk[top]+2){
            len+=2,--top;
            ans=std::max(ans,len);
            continue;
        }
        if(seq[i]==40||seq[i]==91||seq[i]==123) stk[++top]=seq[i];
        else top=len=0;
    }
    printf("%d\n",ans);
    return 0;
}

巴特西

CH1801 括号画家

题意

分析

代码

最新文章

热门文章