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

米奇奇米 · 2019-06-19 22:35:09 · 题解

一道很好的细节模拟题！

1.1题目大意：

求出最长的括号匹配序列，并且输出该序列！

2.1思路理解

这道题目的思路很暴力。用一个数组stak[i][1/2]模拟栈存储。若为stak[i][1]代表一个未匹配完全的字符，stak[i][2]表示这个字符的位置。于是就开始O(n)暴力扫一遍，如果当前的字符与栈顶元素匹配，于是把这个字符以及与他匹配的字符的vis[i]标记为1。如果不匹配，把它也入栈即可。最后再O(n)扫一遍求出的vis[]最长1出现个数。

3.1代码实现

#include <bits/stdc++.h>
using namespace std;
const int length=1e6+5;
char ch[length]; 
int stak[length][3];//stak[][1]表示字符,stak[][2]表示位置 
int n,vis[length],res,l,r,top,now,tmp;
int main() {
    const int xjh=1e6;
    scanf("%s",ch+1);
    int len=strlen(ch+1);
    for ( int i=1;i<=len;i++ ) {
        if((stak[top][1]=='[' && ch[i]==']') || (stak[top][1]=='(' && ch[i]==')')) 
            vis[i]=vis[stak[top--][2]]=1;
        else stak[++top][1]=ch[i],stak[top][2]=i;
    }
    for ( int i=1;i<=len;i++ ) {
        if(vis[i]==1) now=now+1;
        if(vis[i]==0) {
            if(now>res) l=(i-now),r=(i-1),res=r-l;
            now=0;
        }
    }
    for ( int i=l;i<=r;i++ ) putchar(ch[i]);
    return 0;
}

4.1总结

这是一题很好的模拟题。主要是思路的转换，代码实现也很简单。但是我想问巨佬们一个问题：为什么我与第一篇题解对排不上？是原题数据太弱，还是第一篇题解被hike掉了！