``` #include <bits/stdc++.h> using namespace std; int main() { int k; cin >> k; // 输入K值 string a; cin >> a;//输入字符串 char x,y; cin >> x >> y;//输入两个字符 vector<int> dp(a.size());//定义DP数组 //DP数组的含义是，截至字符串下标为i的字符（包括下标为i的字符）一共有多少个首字符c1 dp[0] = a[0] == x;//判断字符串的开头是不是首字符 long long int jie = 0;//存储结果 for(int i = 1;i < a.size();i++) { if(a[i] == x) { dp[i] = dp[i-1] + 1;//如果是首字符就更新dp数组 } else { dp[i] = dp[i - 1];//如果不是首字符dp数组就是前一个的值 if(a[i] == y && i >= k - 1)//如果是尾字符且前k个在有效范围内，则更新结果 jie += dp[i - k + 1];//加上截至第i-k+1个字符中有多少的首字符 } } cout << jie;// 输出结果 } ```

``` #include <iostream> #include <string> using namespace std; int main() { int k, cnt = 0; string s; char c1, c2; long long ans = 0; cin >> k >> s >> c1 >> c2; int n = s.size(); for (int i = n - k, j = n - 1; i >= 0; i--, j--) { if (s[j] == c2) cnt++; if (s[i] == c1) ans += cnt; } cout << ans << endl; return 0; } ```

``` #include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 10; vector<int> x, y; int k; signed main() { cin >> k; string s; char a, b; cin >> s >> a >> b; for(int i = 0; i < s.size(); i ++ ) { if(s[i] == a) x.push_back(i); if(s[i] == b) y.push_back(i); } int ans = 0; for(int i = x.size() - 1, j = y.size() - 1; i >= 0; i -- ) { while(x[i] + k - 1 <= y[j] && j >= 0) j -- ; ans += y.size() - j - 1; } cout << ans; } ```

浅浅一个二分优化 ``` #include<bits/stdc++.h> using namespace std; long long k,a[5000005],b[5000005],ca,cb,ans; string st; char c1,c2; int ef(int x) { int l=1,r=cb,mid,ann; while(l<=r) { mid=(l+r)/2; if(b[mid]-x+1>=k) { ann=mid; r=mid-1; } else l=mid+1; } if(b[ann]-x+1<k)return -1; else return ann; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>k; cin>>st>>c1>>c2; for(int i=0;i<st.size();i++) { if(st[i]==c1) { ca++; a[ca]=i+1; } if(st[i]==c2) { cb++; b[cb]=i+1; } } for(int i=1;i<=ca;i++) { int wz=ef(a[i]); if(wz==-1)continue; else { ans+=cb-wz+1; } } cout<<ans; } ```

``` #include <bits/stdc++.h> using namespace std; int K,cnt; long long ans; string Str; int main() { char a,b; cin >> K>>Str>>a>>b; int S=Str.length(); for(int i=S-K,j=S-1;i>=0;i--,j--) { if(Str[j]==b) cnt++; if(Str[i]==a) ans+=cnt; } cout << ans; return 0; } ```

``` #include<bits/stdc++.h> using namespace std; #define int long long const int N=5e5+5; int k; string str; char c1,c2; int a[N],b[N]; int ans; signed main(){ cin>>k; cin>>str>>c1>>c2; int cnt1=0,cnt2=0; for(int i=0;i<(int)str.size();i++){ if(str[i]==c1) a[cnt1++]=i; else if(str[i]==c2) b[cnt2++]=i; } int j=0; for(int i=0;i<cnt1;i++){ for(;j<cnt2;j++){ if(b[j]-a[i]+1>=k){ ans+=cnt2-j; break; } } } cout<<ans<<endl; return 0; } ```

``` #include <bits/stdc++.h> using namespace std; const int N=5e5+10; int k,cnt[N],t; //cnt用于记录这个点及之后有多少个b long long ans; string str; char a,b; int main(){ cin>>k; cin>>str>>a>>b; int len=str.size(); for(int i=len-1;i>=0;i--){ if(str[i]==b){ t++; cnt[i]=t; } else cnt[i]=t; } for(int i=0;i<=len-k;i++){ if(str[i]==a){ ans+=cnt[i+k-1]; } } cout<<ans<<endl; return 0; } ```

前缀和 ``` #include<bits/stdc++.h> #include<vector> using namespace std; typedef long long ll; int k; string s; char c1,c2; int main() { ios::sync_with_stdio(0);cin.tie(0); cin>>k>>s>>c1>>c2; int sum_c1 = 0; int n = s.size(); ll ans = 0; for(int i = k-1,j = 0;i<n;++j,++i) { if(s[j] == c1) { ++sum_c1; } if(s[i]==c2) { ans += sum_c1; } } cout<<ans<<endl; return 0; } ```

前缀和 ``` #include<bits/stdc++.h> using namespace std; int n,l,c[500005]; long long sum; char s[500005],a,b; int main(){ scanf ("%d\n%s %c %c",&n,s+1,&a,&b); l=strlen(s+1); for(int i=1;i<=l;i++){ if (s[i]==a) c[i]++; c[i]+=c[i-1]; if (i>=n&&s[i]==b){ sum+=c[i-n+1]; } } cout<<sum; return 0; } ```

树状数组 ``` #include <set> #include <map> #include <queue> #include <stack> #include <deque> #include <cmath> #include <vector> #include <cstring> #include <iostream> #include <algorithm> #include <functional> #define int long long #define lowbit(x) x & -x; using namespace std; typedef pair<int,int> PII; const int INF = 1e9,N = 1e6 + 10; int tr[N]; int n; void change(int x,int val) { while(x <= n) tr[x] += val,x += lowbit(x); } int query(int x) { int t = 0; while(x) t += tr[x],x -= lowbit(x); return t; } void solve() { int k; cin >> k; string s; cin >> s; n = s.size(); char l,r; cin >> l >> r; int ans = 0; for(int i = 0;i < n;i++) { if(s[i] == l) change(i + k - 1,1); if(s[i] == r) ans += query(i); } cout << ans << endl; } signed main() { cin.tie(nullptr),ios :: sync_with_stdio(false),cout.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); system("pause"); return 0; } ```