题解：CF1941C（C. Rudolf and the Ugly String）

题解：CF1941C（C. Rudolf and the Ugly String）

题目翻译：给定一个字符串，请你求出最少需要删除几个字符才能使得该字符串内不存在 map 和 pie。

我们可以先在该字符串内找到所有的子串 mapie，并删除中间的 p，这样可以用删除 $1$ 个字符的代价干掉一个 map 和一个 pie（共两个）。显然这样的字符串不会重叠出现。

之后，剩下的所有 map 和 pie 都不存在重叠。这时，我们可以找到所有的子串 map 和 子串 pie，并删去中间的 a 或 i，这样我们可以用删除 $1$ 个字符的代价干掉一个 map 或一个 pie（共一个）。

显然，这样选是最优的。

我们该如何实现呢？我们不能真的用字符串去模拟删除操作，但是我们可以通过枚举形如 mapie、map 和 pie 的子串的数量得出。具体的，记 map 和 pie 的总数量为 $ans$，mapie 的数量为 $ans2$ ，正常情况下答案应该为 $ans+ans2$，但由于每出现一个 mapie 就会对应的出现一组 map 和 pie，而我们并没有进行去重，所以每个 mapie 在计算 $ans2$ 之前就已经被统计了两次，所以应该减去一次，即最终的答案应该是 $ans-ans2$。

代码：

#include<bits/stdc++.h>
using namespace std;
int t;
string x;
int main(){
	scanf("%d",&t);
	while(t--){
		cin>>x>>x;
		int l=x.size(),ans=0,ans2=0;
		for(int i=1;i<l-1;i++){
			if(x[i-1]=='m'&&x[i]=='a'&&x[i+1]=='p'){
				ans++;
			}
			if(x[i-1]=='p'&&x[i]=='i'&&x[i+1]=='e'){
				ans++;
			}
			if(i!=1&&i!=l-2){
				if(x[i-2]=='m'&&x[i-1]=='a'&&x[i]=='p'&&x[i+1]=='i'&&x[i+2]=='e'){
					ans2++;
				}
			}
		}
		printf("%d\n",ans-ans2);
	}
	return 0;
}