每日一题-哞叫题(蓝桥杯）【模拟】
题目要求
我的题目思路
1.输入 N和F
2.输入 竞赛字符串，把竞赛字符串放进字符串数组中
3.设置 p,q指针，设置temp放移动前p所指的字符，设置25个位置的字符串数组B，设置res=0
4.设置循环，条件是q指向的不是字符串的最后一个字母。p指向第一个字符，q指向第二个字符
5.如果p==q，则看temp中有没有放字符【有则看temp中的字符是否=q中字符，不是则把temp+p所指的字符两个按照首字母放在字符串B中且res++，没有则不放】
6.如果p不等于q，则temp保留p所指的字符，且p和q各后移一格
7.循环结束后，如果res>=F,则依次输出字符串B中的所有字符
【思路在题目理解上存在错误，abb是一种叫，cdd也是一种叫，题目的意思是某一种叫的次数>f】
【没有考虑题目中给的字符串有可能跟原字符串有一个字母的错误】
比较简单的题目思路
- 输入 N和F
- 输入 竞赛字符串，把竞赛字符串放进字符串数组中
- 设置con[N][N]计算abb出现次数，st[N][N]计算abb出现次数>f次的次数
- 写一个函数计算类似abb字符串出现的次数，如果abb>f，st[a][b]=true
- 计算原字符串中的 贝茜叫的次数
- 替换原字符串的每一个位置 成不同的字母，重新统计贝茜叫的次数。替换后还原现场
- 统计所有abb>f的次数res,输出res
- 输出所有的abb
代码
#include <iostream> // 引入输入输出库，让程序能够与用户进行交流，比如输出文字到屏幕、接收用户输入等
#include <cstring> // 引入字符串处理库，提供对字符串（一串字符组成的文本）进行操作的功能，比如复制、比较等
#include <algorithm> // 引入算法库，提供一些常用的算法，比如排序、查找等，方便对数据进行处理
using namespace std; // 使用标准命名空间，这样在使用库中的功能时就不用每次都写“std::”前缀了，让代码更简洁
const int N=20010,M=26;//标记字符串的最大值N(题目要求)，最多出现的字母数M=26
int n,f;//定义需要输入的变量
char s[N];//定义需要输入的字符串,长度为 N，因为最大长度=N
int con[M][M];//一次叫为abb，第一个M表示a, 第二个M表示b，定义每个abb出现的次数
int st[M][M];//同上，定义每个abb出现次数>f的，次数>f则为true
void update(int l,int r,int v){
//辅助函数，判断从l位置开始到r位置的字符串中是否存在abb，v表示出现abb时，计数是+1/-1
l=max(l,0),r=min(r,n-1);
//防止越界，如果l比0小取0，如果r比n-1大取n-1
for(int i=0;i+2<=r;i++){
//取l到r中相邻的三个字母
char a=s[i],b=s[i+1],c=s[i+2];
if(a!=b&&b==c){
//判断是否是abb ，如果是
con[a][b]+=v;
//如果是，则abb出现的次数+v
if(con[a][b]>=f){
st[a][b]=true;
//abb出现次数超过f次，st=true
//每次update都会把可能的abb>f次的字符串记录成true
}
}
}
}
int main(){
scanf("%d%d%s",&n,&f,s);//输入字符串长度，叫数的限制，字符串
for(int i=0;i<n;i++) s[i]-='a'; //为了方便比较，把字符串中的每个字母变为数字（-'a'）
update(0,n-1,1);
//查整个串中的abb字符
//[以下是为了检查如果输入字符串跟原字符串存在一个字母错误，更改后的字符串中有多少abb]
for(int i=0;i<n;i++){
//遍历所有字符串中的位置
char t=s[i];//把原字符记录下来
update(i-2,i+2,-1);
//原字符修改只会影响附近的两个字符组成的abb，把原字符组成的abb次数-1复原去计算修改后字符串中的abb
//如果不-1,则把修改前原字符串中的abb次数算进去了
for(int j=0;j<26;j++){
if(j!=t){
//如果修改后的字母跟原字母不同
s[i]=j;//先替换
update(i-2,i+2,1); //更新修改后的abb次数
update(i-2,i+2,-1);//复原现场，还是变成原字符串中abb次数-1
}
}
s[i]=t;//不修改i这个位置的字符了，修改其他位置的字符前先还原修改前的样子
update(i-2,i+2,1);//回复i位置还是t字符时的abb次数
}
int res=0;
for(int i=0;i<26;i++){
for(int j=0;j<26;j++){
if(st[i][j])//记录所有abb次数>=f出现的次数
res++;
}
}
printf("%d\n",res);//输出贝茜叫声出现次数
for(int i=0;i<26;i++){
for(int j=0;j<26;j++){
if(st[i][j])
printf("%c%c%c\n",i+'a',j+'a',j+'a');//输出abb
}
}
return 0;
}