题解：P9244 [蓝桥杯 2023 省 B] 子串简写

· · 题解

题目理解

这道题要求我们统计字符串中所有满足特定条件的子串数量，具体来说：

  1. 子串必须以字符 c_1 开头，以字符 c_2 结尾、
  2. 子串的长度必须 ≥ K（即首尾字符之间的字符数 ≥ K-2）

解题思路

这道题一看，暴力就是不可行的
最直观的想法是枚举所有可能的子串，然后检查它们是否符合条件。但是这种方法的时间复杂度是 O(n²)，对于长字符串（比如长度 50 万）会非常慢，无法通过所有测试用例。

优化方法

我们可以采用更聪明的方法：

  1. 首先遍历字符串，记录所有 c_1 出现的位置和所有 c_2 出现的位置
  2. 然后对于每一个 c_1 的位置，计算有多少个在它后面的 c_2 满足两者之间的距离 ≥ K-1
  3. 使用前缀和或二分查找来快速计算这个数量

具体步骤

  1. 收集位置信息：
    遍历字符串，记录所有 c_1 出现的位置（存入数组 pos1）
    记录所有 c_2 出现的位置（存入数组 pos2）

  2. 计算有效子串数量：
    对于每一个 c_1 的位置 i，我们需要找到在它后面（即位置 > i）的所有 c_2 的位置 j，使得 j - i + 1 >= K
    这等价于找到 pos2 中所有 ≥ i + K - 1 的元素数量
    可以使用二分查找快速计算这个数量

  3. 累加结果：

将所有 c_1 位置对应的有效 c_2 数量累加，得到最终答案

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int K;
    string S;
    char c1, c2;

    cin >> K >> S >> c1 >> c2;

    vector<int> pos1, pos2;

    // 收集所有c1和c2的位置
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == c1) pos1.push_back(i);
        if (S[i] == c2) pos2.push_back(i);
    }

    long long ans = 0;
    int n = pos2.size();

    for (int i : pos1) {
        // 计算在i后面且距离足够的c2的最小位置
        int min_j = i + K - 1;
        // 使用二分查找找到第一个≥min_j的c2位置
        auto it = lower_bound(pos2.begin(), pos2.end(), min_j);
        // 这个位置及之后的所有c2都满足条件
        ans += pos2.end() - it;
    }

    cout << ans << endl;
    return 0;
}

这题也不是很简单

加油！！！