二分写法 $O(nlogn)$
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long LL; //本题数据范围很大 要用LL储存 建议以后做题答案都开成long long
LL res;
string s, a, b;
int k, l[N], r[N]; //我们用l[]来存原字符串中符合起点要求的字母的 坐标 r[]来存原字符串中符合终点要求的字母的 坐标
int main()
{
//关流
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> k >> s >> a >> b;
int t = 0, u = 0;
for (int i = 0; i < s.size(); i ++ ) //遍历字符串 将满足条件的起点终点坐标存入对应数组
{
if (s[i] == a[0]) l[ ++ t] = i; //将满足要求的起点坐标在字符串里的下标存入l[] 注意这里先++的原因是 后面我们要利用t和u作为二分的范围 t++会导致最后一个终点范围向外多加一个1
if (s[i] == b[0]) r[ ++ u] = i; //注意!这里也写成if的原因是起点与终点可能是同样的字母 写成else就不能将坐标也存入r数组了
}
//开始二分
for (int i = 1; i <= t; i ++ ) //先固定一个起点对不同终点进行二分 找到满足条件的最左边的终点 这样在这个点右边的点都是满足k的条件的
{
int ll = 1 , rr = u; //二分的范围就是到数组r[]最后一个元素的范围 l[]数组从1开始存的起点原坐标
while (ll < rr) //找的是左边界
{
int mid = ll + rr >> 1;
if (r[mid] - l[i] >= k - 1) rr = mid; //这里的check(mid)是满足 终点原坐标-起点原坐标 >= k - 1也就是题目要求的最小长度 (坐标相减会多减)
else ll = mid + 1;
}
if (r[ll] - l[i] >= k - 1) res += u - ll + 1; //二分找到了第一个符合条件的终点下标,其后边的终点肯定符合条件 将其后的全部终点个数全部加到答案里
//这里的特判条件是防止一个符合条件的终点下标都没有找到把全部终点个数都输出了
}
cout << res << endl;
return 0;
}
错误代码纪念 过4/10个数据
#include <bits/stdc++.h>
using namespace std;
int k;
string s, a, b;
int res;
int main()
{
scanf("%d", &k);
cin >> s >> a >> b;
deque<int> q;
//for (int h = 0; h < s.size(); h ++ )
//{
for (int i = k; i <= s.size(); i ++ )
{
q.clear();
for (int r = 0; r < i; r ++ ) q.push_back(s[r] - '0');
for (int j = i; j <= s.size(); j ++ )
{
if (q.front() == (a[0] - '0') && q.back() == (b[0] - '0') )
{
res ++ ;
}
q.pop_front();
q.push_back(s[j] - '0');
//for (int h = 0; h < q.size(); h ++ ) cout << q[h] << " " ;
//cout << endl;
}
//cout << res << " ";
}
//}
cout << res << endl;
return 0;
}