题解：UVA10567 Helping Fill Bates

Bobi2014 · 2025-10-04 22:22:06 · 题解

这是一道可癌的二分题。

前置知识

• vector
• upper_bound

思路

考虑使用 vector 存储每个字母出现的位置，严格递增存储，在查询时使用 upper_bound，枚举每个字符，找当前字母且比当前下标大的最小下标，如果枚举时出现了没找到，那么就输出 Not matched，如果找到了最后就输出答案。

Code

#include<bits/stdc++.h>
using namespace std;
int n,Q;
string str;
vector<int> id[52];
int jump(int pos,char c){
    int k = 0;
    if(c >= 'a' and c <= 'z'){
        k = c - 'a';
    }else{
        k = c - 'A' + 26;
    }
    int res = upper_bound(id[k].begin(),id[k].end(),pos) - id[k].begin();
    if(res == id[k].size()){
        return -1;
    }
    return id[k][res];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> str >> Q;
    n = str.size();
    str = " " + str;
    for(int i = 1;i <= n;i ++){
        if(str[i] >= 'a' and str[i] <= 'z'){
            id[str[i] - 'a'].push_back(i);
        }else{
            id[str[i] - 'A' + 26].push_back(i);
        }
    }
    while(Q --){
        cin >> str;
        int m = str.size(),pos = -1;
        str = " " + str;
        for(int i = 1;i <= m;i ++){
            pos = jump(pos,str[i]);
            if(pos == -1){
                break;
            }
        }
        if(pos == -1){
            cout << "Not matched\n";
        }else{
            cout << "Matched " << jump(-1,str[1]) - 1 << " " << pos - 1 << "\n";
        }
    }
    return 0;
}