3154: 蓝桥杯2023年第十四届省赛真题-子串简写

解题思路:

    在本子上手写模拟一下就出来了。以c2为结尾，记录当前有多少个c2，存在dp数组内

    以c1为开头，循环寻找c1，从c1到结尾的c2个数存在dp[i]内，相减就是c2个数，再留出k位数的条件，这个手写模拟一下就知道从c1的下标i到结尾(字符串长度为len,以0为开头)，至少K位后的个数为dp[len-1-i-k+2]

注意事项:

参考代码:

#include<iostream>

#include<cstring>

using namespace std;

const int N=5e5+10;

int k;    

long long dp[N];                //dp[i]为前i位结尾数c2的个数

long long ans;                   // 总数开long long 不然有一个点错误

string s1;

char c1,c2;

int main(){

cin>>k;

cin>>s1>>c1>>c2;

int len=s1.size();

for(int i=0;i<len;i++){

if(s1[i]==c2) dp[i]=dp[i-1]+1;

else dp[i]=dp[i-1];

}

for(int i=0;i<len-k+1;i++){

if(s1[i]==c1) ans+=dp[len-1]-dp[i+k-2];

}

cout<<ans;

return 0;

}