当前位置：首页 > news >正文

14届蓝桥杯 C/C++ B组 T7 子串简写（字符串）

news 2025/8/23 4:41:44

在这里插入图片描述

采用存储目标字符下标的方法，此题的想法比较新奇，故予以记录。

存好下标之后，可以先定位好启始的字符，然后去搜结尾字符符合长度k并且最靠近启始字符的下标，找到之后可以直接取到这个下标之后的所有下标，因为都满足了长度大于等于k。

代码：

#include<iostream>
#include<vector>
using namespace std;
const int N = 5e5 + 10;int main() {//读入int k; cin >> k;string str; cin >> str;char c1, c2; cin >> c1 >> c2;//a1存是字符c1的下标，a2存是字符c2的下标vector<int>a1;vector<int>a2;//存for (int i = 0; i < str.length(); i++) {if (str[i] == c1)a1.push_back(i);if (str[i] == c2)a2.push_back(i);}long long res = 0;//开longlong存答案for (int i = 0; i < a1.size(); i++) {//扫所有的c1对应的下标int t = a1[i];		//先取出c1对应下标int c = t + k - 1;	//定义出满足和c1距离k的下标//二分，从0二分到存c2下标的数组的长度int l = 0, r = a2.size() - 1;	while (l < r) {int mid = l + r >> 1;if (a2[mid] >= c)r = mid;	//如果当前c2的下标是大于等于最近的位置，就去搜更小的else l = mid + 1;}//这里直接取a2的长度减去l，l在这里代表的是a2的下标//通过上面的二分，l已经是最靠近c1的了，所以这就是能够取到的最长的长度了if (a2[l] >= c)res += a2.size() - l;}cout << res;return 0;
}