蓝桥杯b组 G
大家帮我看看呜呜呜
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N = 5e5 + 10;
int k;
string a;
char x,y;
int xid[N];
int idx = 0;
void solve()
{
cin >> k;
cin >> a;
cin >> x >> y;
int len = a.length();
int res = 0;
for(int i = 0;i < len;i ++)
{
if(a[i] == x)
{
xid[idx ++] = i;
//cout << i << endl;
}
if(a[i] == y)
{
if(i - k + 1 < 0) continue;
int l = 0;int r = idx;
while(l < r - 1)
{
int mid= (l + r)/2;
if(xid[mid] > i - k + 1) r = mid;
else l = mid;
}
//cout <<i << ' ' << l << endl;
res += l + 1;
}
}
cout << res << endl;
}
int main()
{
solve();
return 0;
}
有没有可能用前缀和做更快?
没看出来前缀和