题解 P1241 【括号序列】

_蒟蒻—信含_ · 2019-10-05 09:48:07 · 题解

这题好像是luogu夏令营中的一个例题……

好啦，第五篇题解

初看此题，我惊了 这题是绿题？？？？？

不慌，先来波代码压压惊

#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<iomanip>
using namespace std;
char kh[111],sx[111],x;
int bj=0,hh,qzzkh=0;
int main()
{
    while(cin>>x)
    {
        kh[++bj]=x;
        x=0;
     }
    hh=bj;
    for(int i=1;i<=bj;i++)
    {
        if(kh[i]=='('||kh[i]=='[')
        {
            hh++;
            qzzkh++;//前置左括号
        }
        if(kh[i]==')'||kh[i]==']')
        {
            if(kh[i]==')'&&kh[i-1]=='('||kh[i]==']'&&kh[i-1]=='[')
            {
                sx[(qzzkh-1)*2+1]=kh[i-1];
                sx[qzzkh*2]=kh[i];
                kh[i]=kh[i+2];
                kh[i-1]=kh[i+1];
             }
        }
    }//防抄水印
    for(int i=1;i<=hh;i++)
    {
        if(sx[i]==0)
        {
            if(sx[i-1]=='(') sx[i]=')';
            else sx[i]=']';
        }
    }
    for(int i=1;i<=hh;i++)
        cout<<sx[i];
    return 0;
}

用数组做竟然WA了！！！！！！！！！！！！！！！！

紧急去复习了一下栈……后来改成了这样(改了50多………………分钟)

//对不起，为了反抄袭，我把头文件删了
using namespace std;
char a[210],b[210],cxk[5]= {']',')','0','(','['};//cxk用来判断括号形状
int jntm[666];//jntm用来替换括号等
int main()//防抄水印
{
    int n;
    stack<int> st;
    int afg,j=0;
    scanf("%s",s);
    afg=strlen(s);
    jntm['(']=-1;jntm[')']=1;jntm['[']=-2;jntm[']']=2;
    for (int i=0; i<afg; i++) 
    {
        char c=s[i];
        if(jntm[c]<0) st.push(i);//防抄水印
        else 
        {
            if(!st.empty())
            {
                int k=st.top(); 
                if(jntm[s[k]]+jntm[c]==0)b[i]=b[k]=1,st.pop();
            }
        }//防抄水印
    }
    for(int i=0;i<afg;i++)
        if(b[i])cout<<s[i];//防抄水印
        else
        {
            int k=jntm[s[i]];
            if(k<0)cout<<s[i]<<tj[4+k];
            else cout<<tj[4+k]<<s[i];
        }//防抄水印
}//信含原创防抄水印

呵呵，才得15分……

翻了一下资尿 oh,不，不要误会，是资料，改成了AC代码

（依然有防抄水印）

//对不起，为了反抄袭，我把头文件删了
using namespace std;
char a[210],b[210],cxk[9]={'>','}',']',')','0','(','[','}','<'};//只不过增加了几个判断
int jntm[250];
int main()
{
    int n;
    stack<int> st;//防抄水印
    int afg,j=0;
    scanf("%s",a);
    afg=strlen(a);
    jntm['(']=-1;jntm[')']=1;jntm['[']=-2;jntm[']']=2;jntm['{']=-3;jntm['}']=3;jntm['<']=-4;jntm['>']=4;//防抄水印
    for (int i=0; i<afg; i++)
    {
        char c=a[i];
        if(jntm[c]<0) st.push(i);
        else //防抄水印
        {
            if(!st.empty())
            {
                int k=st.top();//防抄水印 
                if(jntm[a[k]]+jntm[c]==0)b[i]=b[k]=1,st.pop();
            }
        }
    }
    for(int i=0; i<afg; i++)//防抄水印
        if(b[i])cout<<a[i];
        else
        {
            int k=jntm[a[i]];
            if(k<0)cout<<a[i]<<cxk[4+k];
            else cout<<cxk[4+k]<<a[i];//防抄水印
        }
}//信含原创，防抄水印

如果看不懂的话，就请私聊我吧！

我的第一个AC绿题呀！