专栏文章

题解:P3333 [ZJOI2013] 丽洁体

P3333题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miogo15u
此快照首次捕获于
2025/12/02 18:54
3 个月前
此快照最后确认于
2025/12/02 18:54
3 个月前
查看原文

P3333 丽洁体

题目概括

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

思路

其实这道题可以暴力匹配,只是读入部分稍微难一点。
先从头匹配找到不规范作品 ll 中的 aa 串,答案加上多出来的词,记录 aa 串的末尾 azuiazui
再从后匹配 ll 中的 cc 串,也记录答案,记录 cc 的起始 czuiczui
最后从 azuiazuiczuiczui 匹配 bb 串,记录答案 ansbansb
这里有个小细节:在匹配 bb 串的时候可能有多个起始点,枚举起点然后在每个答案里取个最小值就行。
最后输出两个答案之和即可。

代码

CPP
#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;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...