蓝桥杯每日一题2023.9.22

4960. 子串简写 - AcWing题库

题目描述

题目分析 

原本为纯暴力但是发现会超时，可以加入前缀和，从前往后先记录一下每个位置c1出现的次数

再从前往后扫一遍，如果遇到c2就将答案加上此位置前的所有c1的个数（直接加上此位置的前缀和）

纯暴力：

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll ans; int main() { ll k; string s; char c1, c2; cin >> k; cin >> s; cin >> c1 >> c2; ll len = s.size(); for(ll i = 0, j = 1; i < len - 1; i ++) { if(s[i] == c1) { j = i + 1; while((s[j] != c2 || j - i + 1 < k) && j < len - 1) { j ++; } if(s[j] == c2 && j - i + 1 >= k) { ans ++; while(j < len - 1) { j ++; if(s[j] == c2) { ans ++; } } } } } cout << ans; return 0; }

 ac代码：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e5 + 10; ll k, ans, s[N]; string c; char c1, c2; int main() { cin >> k; cin >> c; cin >> c1 >> c2; ll len = c.size(); for(int i = 0; i < len; i ++) { if(c[i] == c1) { s[i + 1] = s[i] + 1; } else s[i + 1] = s[i]; } for(int i = k - 1; i < len; i ++)//注意长度至少为k { ll l = i - k + 1; if(c[i] == c2)ans += s[l + 1]; } cout << ans; return 0; }