首页 > 代码库 > Codefroces 223A - Bracket Sequence【栈优化】

Codefroces 223A - Bracket Sequence【栈优化】

2024-07-19 15:15:39   217人阅读

题目大意：

有一串只含有 "("  ")"  "["  "]" 的序列，问在该序列的 左右括号能分别配对的 所有子串中的含有方括号的个数的最大值，并输出相对应的子串。

做法：

利用一个栈来维护，每次如果有能与栈顶的元素配对的右边括号时，将该元素弹出，如果此时弹出的元素代表方括号，那么记录此时出现的下标。否则将该元素压进栈。
当然我们压进栈的是当前元素的下标。当处理完整个序列之后，栈里面存的就是所有不能配对的括号所处的下标，每两个下标之间就是能配对的，符合条件的。这样，我们最后只需要比较每两个下标之间含有的能含有方括号最多即可。而计算某个片段有多少个方括号的话，我们只需要利用之前记录的方括号的下标，计算一个前缀和，就能很方便的算出来了

代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 110010
using namespace std;
char a[N];
int sta[N];
int vis[N];
int ans,l,r;
int main()
{
    scanf("%s",a);
    int len=strlen(a);
    int tail=1;
    for(int i=0;i<len;i++)
    {
        if(tail==1) {
            sta[tail++]=i;
            vis[i]+=vis[i-1];
            continue;
        }
        if(a[i]=='(')
        {
            sta[tail++]=i;
        }
        if(a[i]==')')
        {
            if(a[sta[tail-1]]=='(') tail--;
            else sta[tail++]=i;
        }
        if(a[i]=='[')
        {
            sta[tail++]=i;
        }
        if(a[i]==']')
        {
            if(a[sta[tail-1]]=='[') {
                tail--;
                vis[i]=1;
            }
            else sta[tail++]=i;
        }
        vis[i]+=vis[i-1];
    }
    vis[len]+=vis[len-1];
    if(tail==1)
    {
        cout<<vis[len]-vis[0]<<endl;
        cout<<a<<endl;
        return 0;
    }
    sta[tail++]=len;
    sta[0]=0;
    for(int i=1;i<tail;i++)
    {
        if(ans<vis[sta[i]]-vis[sta[i-1]])
        {
            ans=vis[sta[i]]-vis[sta[i-1]];
            if(i-1) l=sta[i-1]+1;
            else l=0;
            r=sta[i];
        }
    }
    cout<<ans<<endl;
    for(int i=l;i<r;i++)
        cout<<a[i];
    return 0;
}


Codefroces 223A - Bracket Sequence【栈优化】


联系
我们