题解：P3333 [ZJOI2013] 丽洁体

yytmcjs · 2025-08-08 11:09:41 · 题解

P3333 丽洁体

题目概括

有一个规范的格式：前（任意）中（任意）后。要求在给出的文段中删去最少的词使得其满足这个要求。

思路

其实这道题可以暴力匹配，只是读入部分稍微难一点。

先从头匹配找到不规范作品 l 中的 a 串，答案加上多出来的词，记录 a 串的末尾 azui。

再从后匹配 l 中的 c 串，也记录答案，记录 c 的起始 czui。

最后从 azui 至 czui 匹配 b 串，记录答案 ansb。

这里有个小细节：在匹配 b 串的时候可能有多个起始点，枚举起点然后在每个答案里取个最小值就行。

最后输出两个答案之和即可。

代码

#include <bits/stdc++.h>
using namespace std;

int ans,llen,alen,blen,clen,ansb=0x3f3f3f3f;

int main(){
    int azui,czui;
    string l[60005];
    string a[60005],b[60005],c[60005];
    cin >> l[++llen];
    while(getchar() == ' '){
        cin >> l[++llen];
    }
    cin >> a[++alen];
    while(getchar() == ' '){
        cin >> a[++alen];
    }
    cin >> b[++blen];
    while(getchar() == ' '){
        cin >> b[++blen];
    }
    cin >> c[++clen];
    while(getchar() == ' '){
        cin >> c[++clen];
    }
    int o=1;
    for (int i=1;i<=llen;i++){
        if (l[i]==a[o]){
            o++;
        }
        if (o>alen){
            azui=i;
            ans+=azui-alen;
            break;
        }
    }
    o=clen;
    for (int i=llen;i>=1;i--){
        if (l[i]==c[o]){
            o--;
        }
        if (!o){
            czui=i;
            ans+=llen-czui+1-clen;
            break;
        }
    }
    for (int i=azui+1;i<czui;i++){
        if (l[i]==b[1]){
            o=1;
            for (int j=i;j<czui;j++){
                if (l[j]==b[o]){
                    o++;
                }
                if (o>blen){
                    ansb=min(ansb,j-i+1-blen);
                    break;
                }
            }
        }
    }
    ans+=ansb;
    cout << ans;
    return 0;
}