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

题目理解

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

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

解题思路

这道题一看，暴力就是不可行的
最直观的想法是枚举所有可能的子串，然后检查它们是否符合条件。但是这种方法的时间复杂度是

O(n²)

，对于长字符串（比如长度 50 万）会非常慢，无法通过所有测试用例。

优化方法

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

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

具体步骤

收集位置信息：
遍历字符串，记录所有 $c_1$ 出现的位置（存入数组 $pos1$ ）
记录所有 $c_2$ 出现的位置（存入数组 $pos2$ ）
计算有效子串数量：
对于每一个 $c_1$ 的位置 $i$ ，我们需要找到在它后面（即位置 > $i$ ）的所有 $c_2$ 的位置 $j$ ，使得 $j - i + 1$ >= $K$
这等价于找到 $pos2$ 中所有 ≥ $i + K - 1$ 的元素数量
可以使用二分查找快速计算这个数量
累加结果：

将所有

c_1

位置对应的有效

c_2

数量累加，得到最终答案

代码

CPP

#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;
}

~~这题也不是很简单~~

加油！！！

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

文章操作

题目理解

解题思路

优化方法

具体步骤

代码

相关推荐

评论

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