洛谷 P1381 单词背诵

张开发
• 2026/4/18 6:11:33 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

洛谷 P1381 单词背诵
题目描述灵梦有 n 个单词想要背但她想通过一篇文章中的一段来记住这些单词。文章由 m 个单词构成她想在文章中找出连续的一段其中包含最多的她想要背的单词重复的只算一个。并且在背诵的单词量尽量多的情况下还要使选出的文章段落尽量短这样她就可以用尽量短的时间学习尽可能多的单词了。每个单词仅包含小写字母。输入格式第 1 行一个数 n接下来 n 行每行是一个长度不超过 10 的字符串表示一个要背的单词。接着是一个数 m然后是 m 行长度不超过 10 的字符串每个表示文章中的一个单词。输出格式输出文件共 2 行。第 1 行为文章中最多包含的要背的单词数第 2 行表示在文章中包含最多要背单词的最短的连续段的长度。输入输出样例输入 #1复制3 hot dog milk 5 hot dog dog milk hot输出 #1复制3 3说明/提示数据规模与约定对于 30% 的数据n≤50m≤500对于 60% 的数据n≤300m≤5000对于 100% 的数据1≤n≤10001≤m≤105。#includebits/stdc.h using namespace std; unordered_setstring mp; unordered_setstring tmp; const int N1e510; int n,m; int kind; string k[N]; unordered_mapstring,int cnt; int main() { cinn; for(int i1;in;i) { string s; cins; mp.insert(s); } cinm; for(int i1;im;i) { cink[i]; if(mp.count(k[i])) { tmp.insert(k[i]); } } couttmp.size()endl; if(tmp.empty()) { cout0endl; return 0; } int ansN; for(int l1,r1;rm;r) { if(!tmp.count(k[r])) continue; cnt[k[r]]; if(cnt[k[r]]1) kind; while(kindtmp.size()) { ansmin(ans,r-l1); cnt[k[l]]--; if(cnt[k[l]]0) kind--; l; } } coutansendl; return 0; }

更多文章