解题思路:首先字符串是s,两个连接字符是c1和c2而我们可以发现对于每个c1都会有一个c2(下标记为pos)可以使得pos之后的字符串都能满足条件,发现了没有很像二分的思路,先用a,b数组保存c1,c2的下标再选定a[i]对b做二分即可(注意一个都没有的情况说明之后都找不到任意b[i]-a[i]+1>=k了)
注意事项:c1和c2可能相等,保存下标的时候不能用if else结构
参考代码:
#include<iostream>
#include<string>
using namespace std;
string s;
long long int a[500000], b[500000], k, sum = 0, j=0, k1=0;
char t1, t2;
int main()
{
cin >> k >> s >> t1 >> t2;
for (int i = 0; i <= s.size() - 1; i++)
{
if (s[i] == t1)
{
a[j] = i;
j++;
}
if (s[i] == t2)
{
b[k1] = i;
k1++;
}
}
for (int i = 0; i <= j - 1; i++)
{
long long int l = 0, r = k1-1, mid, sum2=k1;
if (b[k1 - 1] - a[i] + 1 < k)
break;
while (l <= r)
{
mid = (l + r) / 2;
if (b[mid] >= a[i]+k-1)
{
r = mid - 1;
sum2 = mid;
}
else
l = mid + 1;
}
sum += k1 - sum2;
}
cout << sum;
}
0.0分
0 人评分
【回文数(二)】 (C语言代码)浏览:732 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:647 |
三角形 (C++代码)递推浏览:760 |
C语言程序设计教程(第三版)课后习题6.5 (C++代码)浏览:458 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:902 |
A+B for Input-Output Practice (III) (C语言代码)浏览:569 |
printf基础练习2 (C语言代码)浏览:508 |
1050题解(结构体数组与结构体指针的使用)浏览:1111 |
前10名 (C语言代码)浏览:727 |
整除问题 (C语言代码)浏览:526 |