P2395 题解

· · 题解

P2395 题解

前置知识

题目解法

算是大模拟，又不能完全算。相比鸭棋来说还是保守了。

模拟的话十分简单，按照题意描述即可，判断是否合法只需要一个栈即可。

但是本题真的只有这样吗？

其实本题真正的难点在于如何读懂题目，以及十分多的坑点，本篇题解将会一一叙述。以下是我找到的全部坑点：

一、url 与 img

关于 url 和 img，两个的内容里面是会有嵌套的，所以不能直接处理，需要一个栈来维护。

二、quote

quote 的处理方式题目中说的并没有多么清楚，那我们在此说明一下。

为了方便处理换行，这里有个小技巧，读入的时候直接把 \r 这种东西不要让它读入进来。

首先，如果 [quote] 前不是换行，需要先换一个行。

然后，如果 [/quote] 后面没有换行，也需要换一个行。

其次，如果 [quote] 后面有换行或者 [/quote] 前面有换行，需要消除掉。具体是只消除前后两个还是全部消除，题目中没有明确说明，我是按后者写的，两种写法都能过。

最后，如果检测到了 [quote]，那其它的标签都不要判断了，只判断 [/quote]。

三、数据范围

输入量大概在 10^6 左右，所以时间复杂度尽量要是 O(n) 的，不然有可能会超时。

剩下的几乎没有坑点了。

AC 代码

#include<iostream>
using namespace std;
char a[4000005],ans[4000005];
int n,zhan[1000005],tot,num,isq,l;
char url[10005][10005];
bool pd(int i,int len,char* c){//判断是否是这个字符串
    for(int j=i;j<i+len;++j){
        if(a[j]!=c[j-i])return 0;
    }
    return 1;
}
void qwq(int x){//不合法判断
    if(zhan[tot]!=x){
        cout<<"Match Error";exit(0);
    }
    else --tot;
}
void add(char c){//往答案里加入字符
    ans[++l]=c;
}
int main(){
    while((a[++n]=getchar())!=EOF){
        if(a[n]=='\r')--n; //别让\r 读入进来！
    }
    a[0]='\n';
    --n;
    for(int i=1;i<=n;){
    //以下是一些简单的判断
        if(isq==0&&pd(i,4,"[h1]")){
            zhan[++tot]=1;
            add('#'),add(' ');
            i+=4;
        }
        else if(isq==0&&pd(i,5,"[/h1]")){
            qwq(1);
            add(' '),add('#');
            i+=5;
        }
        else if(isq==0&&pd(i,4,"[h2]")){
            zhan[++tot]=2;
            add('#'),add('#'),add(' ');
            i+=4;
        }
        else if(isq==0&&pd(i,5,"[/h2]")){
            qwq(2);
            add(' '),add('#'),add('#');
            i+=5;
        }
        else if(isq==0&&pd(i,3,"[i]")){
            zhan[++tot]=3;
            add('*');
            i+=3;
        }
        else if(isq==0&&pd(i,4,"[/i]")){
            qwq(3);
            add('*');
            i+=4;
        }
        else if(isq==0&&pd(i,3,"[b]")){
            zhan[++tot]=4;
            add('_');add('_');
            i+=3;
        }
        else if(isq==0&&pd(i,4,"[/b]")){
            qwq(4);
            add('_');add('_');
            i+=4;
        }
        else if(isq==0&&pd(i,5,"[url=")){
            zhan[++tot]=5;
            ++num;
            int j=0;
            for(j=i+5;j<=n&&a[j]!=']';++j){
                url[num][j-(i+5)]=a[j];
            }
            url[num][j]='\0';
            add('[');
            i=j+1;
        }
        else if(isq==0&&pd(i,6,"[/url]")){
            qwq(5);
            add(']');
            add('(');
            for(int j=0;url[num][j]!='\0';++j){
                add(url[num][j]);
            }
            --num;
            add(')');
            i+=6;
        }
        else if(isq==0&&pd(i,5,"[img=")){
            zhan[++tot]=6;
            ++num;
            add('!');
            int j=0;
            for(j=i+5;j<=n&&a[j]!=']';++j){
                url[num][j-(i+5)]=a[j];
            }
            url[num][j]='\0';
            add('[');
            i=j+1;
        }
        else if(isq==0&&pd(i,6,"[/img]")){
            qwq(6);
            add(']');
            add('(');
            for(int j=0;url[num][j]!='\0';++j){
                add(url[num][j]);
            }
            --num;
            add(')');
            i+=6;
        }
        //重点来啦
        else if(isq==0&&pd(i,7,"[quote]")){
            zhan[++tot]=7;
            isq=1;
            int j=i+7;
            if(a[i-1]!='\n')add('\n');//如果上一个不是换行
            add('>');add(' '); 
            while(a[j]=='\n')++j;//记得往后跳
            i=j;
        }
        else if(pd(i,8,"[/quote]")){
            qwq(7);
            isq=0;
            while(ans[l]=='>'||ans[l]=='\n'||ans[l]==' ')--l;//消除后面换行
            if(a[i+8]!='\n')add('\n');//如果下一个不是换行
            i+=8;
        }
        else{
            add(a[i]);
            if(a[i]=='\n'&&isq)add('>'),add(' ');
            ++i;
        }
    }
    if(tot)cout<<"Unclosed Mark";//记得判一下第二种不合法情况
    else for(int i=1;i<=l;++i)putchar(ans[i]);
    return 0;
}