我是靠谱客的博主 高大雨,这篇文章主要介绍2019 ICPC 南昌邀请赛网络赛 M题 Subsequence(预处理+二分查找),现在分享给大家,希望可以做个参考。

参考来源

https://blog.csdn.net/qq_38735931/article/details/89422093

题目

给你一个主字符串,最大长度为1e5
然后你n个字符串进行询问,n至多1e5,每个字符串最长为1e3
问你这个字符串是不是主字符串的子串(不必连续,但要按顺序)

思路

暴力明显超时。

先对主字符串做预处理,对于每一个字母,把改字母的位置存下来。
用一个vecter 的a[30], a[0]存字母a,a[1]存字母b…………
然后按着给出的子字符串查找字母,用
每次用二分查找( upper_bound() )

不理解的地方

这里的flag我原先是这样写的,不过在交的时候,有时A有时T

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int flag=0; ………………………… ………………………… int tem=ch[i]-'a'; if(a[tem].empty()) { flag=1; break; } ………………………… ………………………… ………………………… if(emm<a[tem].size()&&npos>pos) pos=npos; else { flag=1; break; } ………………………… ………………………… if(flag) NO(); else YES();

换成下面代码那样就不会,而且时间短了至少半秒以上?不太清楚为什么。(可能是它的样例造的不好)

这个算法复杂度是O(nmlogk),n*m的最大值是1e8,给出的字符串最多1e3,那log后小于3,相乘刚好小于3e8,而时间限制3s,(⊙o⊙)…在超时边缘疯狂试探。

代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h> using namespace std; char s[100005]; char ch[1005]; vector<int> a[30]; int main() { scanf("%s",s); int len=strlen(s); for(int i=0;i<len;i++) a[s[i]-'a'].push_back(i);//对应的字母,存位置 int n; scanf("%d",&n); while(n--) { scanf("%s",ch); int ch_len=strlen(ch); if(a[ch[0]-'a'].empty()) { puts("NO"); continue; } int pos=a[ch[0]-'a'][0]; int flag=1; for(int i=1;i<ch_len;i++) { int tem=ch[i]-'a'; if(a[tem].empty()) { flag=0; break; } int emm=upper_bound(a[tem].begin(),a[tem].end(),pos)-a[tem].begin(); if(emm<a[tem].size()&&a[tem][emm]>pos) pos=a[tem][emm]; else { flag=0; break; } } if(flag) puts("YES"); else puts("NO"); } return 0; }

最后

以上就是高大雨最近收集整理的关于2019 ICPC 南昌邀请赛网络赛 M题 Subsequence(预处理+二分查找)的全部内容,更多相关2019内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(69)

评论列表共有 0 条评论

立即
投稿
返回
顶部