专栏文章

题解：UVA10567 Helping Fill Bates

BBobi2014
UVA10567题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minp7fl7
此快照首次捕获于
2025/12/02 06:05
3 个月前
此快照最后确认于
2025/12/02 06:05
3 个月前
查看原文
这是一道可癌的二分题。

前置知识

思路

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

Code

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...