P1944 最长括号匹配_NOI导刊2009提高

题解

宁愿相信世上有鬼，也不能随便相信某谷题目标签

我想了半天然后看了眼题解，发现用栈来模拟就好了

栈来模拟，还要用到一个bool数组，标记是否已经匹配 use[ i ]

一串括号，入栈，遇到匹配的就弹出去，标记已经匹配，然后最后挑连续匹配的最大的就好了，因为题目要求子串

注意两个点：

1.q[top]数组存的是括号的标号，而不是top是存的括号标号

2.res记录暂时一共有多少个连续的匹配括号数，所以每遇到一个新的括号，都要更新一遍

具体可以结合代码

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<string>

#include<cstring>

#include<queue>

using namespace std;

typedef long long ll;

inline int read()

{

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

const int maxn=1e6+;

char s[maxn];

bool use[maxn];

int top=,q[maxn];

int l,r,ans=,res=,l1=,r1=;

int main()

{

    scanf("%s",s+);

    int len=strlen(s+);

    memset(use,,sizeof(use));

    for(int i=;i<=len;i++){

        if((s[q[top]]=='('&&s[i]==')')||(s[q[top]]=='['&&s[i]==']')){

            use[q[top--]]=;

            use[i]=;

        }

        else{

            q[++top]=i;

        }

    }

    for(int i=;i<=len;i++){

        if(!use[i]){

            if(res>ans) ans=res,l=l1,r=r1;

            res=;   //不可以放到if里面

        }

        else{

            if(res==) l1=r1=i;

            else r1++;

            res++;    //不可以放到if里面

        }

    }

    if(res>ans) ans=res,res=,l=l1,r=r1;

    for(int i=l;i<=r;i++) printf("%c",s[i]);

    return ;

}

一开始自己Hank自己然后就被自己 Hank si 了

1.())[]())[]

2.())[]([(][()]]()

巴特西

P1944 最长括号匹配_NOI导刊2009提高（1）

P1944 最长括号匹配_NOI导刊2009提高

题解

注意两个点：

代码

一开始自己Hank自己然后就被自己 Hank si 了

最新文章

热门文章