「CODEVS3013」单词背诵
题目描述 Description
灵梦有n个单词想要背，但她想通过一篇文章中的一段来记住这些单词。
文章由m个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样她就可以用尽量短的时间学习尽可能多的单词了。
输入描述 Input Description
第1行一个数n，
接下来n行每行是一个长度不超过10的字符串，表示一个要背的单词。
接着是一个数m，
然后是m行长度不超过10的字符串，每个表示文章中的一个单词。
输出描述 Output Description
输出文件共2行。第1行为文章中最多包含的要背的单词数，第2行表示在文章中包含最多要背单词的最短的连续段的长度。
样例输入 Sample Input
3
hot
dog
milk
5
hot
dog
dog
milk
hot
样例输出 Sample Output
3
3
数据范围及提示 Data Size & Hint
对于30%的数据 n<=50，m<=500；
对于60%的数据 n<=300，m<=5000；
对于100%的数据 n<=1000，m<=100000；
题解
先用哈希表得出第一问的答案
区间右端点从左往右扫这m个单词，统计每个单词的出现次数
左端点贪心移动，即：若左端点的单词出现次数超过1次，则左端点右移个单词
|
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 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define mod 100007 #define ll long long using namespace std; int n,m,ans,mn=0x7fffffff; bool hash[100008],mark[100008]; int v[100008],num[100008]; string str[100008]; ll get(char ch[]) { ll s=0,k=1; for(int i=0;i<strlen(ch);i++) { s+=k*(ch[i]-'a'); s%=mod;k*=26; k%=mod; } while(hash[s]&&str[s]!=ch) {s++;s%=mod;} return s; } int main() { char ch[11]; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",ch); str[get(ch)]=ch; hash[get(ch)]=1; } scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%s",ch); v[i]=get(ch); if(hash[v[i]]&&!mark[v[i]]) {ans++;mark[v[i]]=1;} } printf("%d\n",ans); int l=1,r=1,tot=0; while(r<=m) { while(r<=m) { if(mark[v[r]]&&!num[v[r]])tot++; num[v[r]]++; r++; if(tot==ans)break; } while((!mark[v[l]]||num[v[l]]>1)&&l<r){num[v[l]]--;l++;} mn=min(r-l,mn); } printf("%d\n",mn); return 0; } |
Subscribe
计数器 9793925
OI 课件=>
OI 课件=>