【前缀和+开区间二分】codeforces 1187 B. Letters Shop

RomanLin / 2024-10-07 / 原文

题意

第一行，输入一个正整数 $n(1 \leq n \leq 2*10^5)$，代表字符串 $s$ 的长度。
第二行，输入一个字符串 $s$。
第三行，输入一个正整数 $m(1 \leq m \leq 5*10^4)$，代表接下来要输入的询问次数，对于每次询问：输入一个字符串 $t(1 \leq |t| \leq 2*10^5)$，并保证 $\sum_{i=1}^m{|t_i|} \leq 2*10^5$。

保证：所有字符串中的字符只包含小写英文字母。

对于每个 $t$，你需要在 $s$ 中找出一个前缀，满足能在该前缀中找出一个子序列，经过任意顺序的调换以后，若能构造出 $t$，则视为一个合法前缀。保证：每个 $t$ 都能在 $s$ 中找到至少一个合法前缀。

对于每个 $t$，输出合法前缀的最短长度。

题解

维护 $s$ 在区间 $(0, n + 1)$ 每个位置上的26个字母的出现频度，然后使用二分法查找出满足每个字母的出现频率都比 $t$ 大的最短合法前缀。

此题保证了每个 $t$ 都能在 $s$ 找到至少一个合法前缀，因此在区间 $(0, n + 1)$ 上必定存在合法解。

问：若没有保证一定有解呢？该如何使用二分法维护答案？
答：使用开区间二分，若返回值落在开区间的边界上，则说明必定无解。

参考代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;

constexpr int N = 26;
int T = 1, n, m;
int a[N];
string s, t;

bool check(int mid, vector<vector<int>>& pre) {
    for (int i = 0; i < 26; ++ i) if (pre[i][mid] < a[i]) return false;
    return true;
}

int main() {
    IOS
    cin >> n >> s;
    vector<vector<int>> pre(26, vector<int>(n + 1));
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < 26; ++ j) pre[j][i + 1] = pre[j][i];
        pre[s[i] - 'a'][i + 1] ++;
    }
    cin >> m;
    while (m --) {
        for (int i = 0; i < 26; ++ i) a[i] = 0;
        cin >> t;
        for (auto &c: t) a[c - 'a'] ++;
        int left = 0, right = n + 1, middle;
        while (left + 1 < right) {
            middle = left + right >> 1;
            (check(middle, pre) ? right : left) = middle;
        }
        cout << right << '\n';
    }
    return 0;
}