題目描述

靈夢有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<=50，m<=500；

對于60%的數據 n<=300，m<=5000；

對于100%的數據 n<=1000，m<=100000；

題解：

本題真是顯示出了pb_ds庫功能的強大。不懂這個庫的可看一下這篇文章：

http://www.cnblogs.com/huihao/p/7137250.html

思路一：

先解決第一問：用兩個哈希表一個記錄必背單詞，一個記錄這個但是是否被背過。

第二問我們發現最多要背單詞的最短的連續段的長度滿足單調性，我們就可以用一個隊列來實現，在隊列中記錄。注意數據中有一個點要特判，因為最多包含的要背的單詞數是0，循環會死在里面的。

我首先想到的使用STL庫中的set寫，因為要保證每個單詞的唯一性。

#include<iostream> #include<cstdio> #include<cstring> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/hash_policy.hpp> #include<set> using namespace std; using namespace __gnu_pbds; gp_hash_table<string,bool>h1; gp_hash_table<string,bool>h2; gp_hash_table<string,int>h3; int n,m,num; char s[101001][20]; set<string> a; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s[i]);h1[s[i]]=1;}scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%s",s[i]);if(h1[s[i]]&&!h2[s[i]]){num++;h2[s[i]]=1;}}int l=1,minn=100000000;for(int i=1;i<=m;i++){if(h1[s[i]]){a.insert(s[i]);h3[s[i]]++;}int tmp=a.size();while(tmp==num){minn=min(minn,i-l+1);if(h1[s[i]]){h3[s[l]]--;if(h3[s[l]]==0) {a.erase(s[l]);tmp--;}}l++;}}printf("%d\n%d\n",num,minn);return 0; }

?思路二；

但后來發現完全沒這個必要，因為set的效率有點低，如果不斷地插入刪除，數據小的話有可能過，數據大的話就卡死了。所以我們可以在開個哈希表記錄每個必背單詞在隊列從中出現的次數。

#include<iostream> #include<cstdio> #include<cstring> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/hash_policy.hpp> using namespace std; using namespace __gnu_pbds; cc_hash_table<string,bool>h1; cc_hash_table<string,bool>h2; cc_hash_table<string,int>h3; int n,m,num; char s[120001][20]; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s[i]);h1[s[i]]=1;}scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%s",s[i]);if(h1[s[i]]&&!h2[s[i]]){num++;h2[s[i]]=1;}}int l=1,minn=100000000;int cnt=0;for(int i=1;i<=m;i++){if(h1[s[i]]){if(!h3[s[i]])cnt++;h3[s[i]]++;}while(cnt==num){if(l==i) {minn=0;break;}minn=min(minn,i-l+1);if(h1[s[l]]){h3[s[l]]--;if(h3[s[l]]==0) cnt--;}l++;}}printf("%d\n%d\n",num,minn);return 0; }

思路三：

哈希+二分，經過優化之后貌似快了一些。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,e,wo; char x[13]; int b[10003]; unsigned long long y[100005]; unsigned long long q[15]; unsigned long long g[1006],t[100005]; inline unsigned long long has(char ss[13]) {unsigned long long tot=0;for(int i=strlen(ss)-1;i>=0;i--){tot+=(ss[i]-'a'+1)*q[i];}return tot; } bool ef(int l,int r,unsigned long long k) {e=(l+r)>>1;if(k==t[e]) return 1;if(l==r) return 0;if(k<t[e]) return ef(l,e,k);else return ef(e+1,r,k); } int ff(int l,int r,unsigned long long k) {e=(l+r)>>1;if(k==g[e]) return e;if(l==r) return 0;if(k<g[e]) return ff(l,e,k);else return ff(e+1,r,k); } void init() {q[1]=1;for(int i=2;i<=13;i++)q[i]=q[i-1]*27;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",&x);g[i]=has(x);}scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%s",&x);t[i]=has(x);y[i]=t[i];} } int main() {int tot=0,z;init();sort(t,t+m+1);for(int i=1;i<=n;i++) if(ef(1,m,g[i])) tot++;printf("%d\n",tot);wo=tot;int l=0,r=0;int mi=m;sort(g,g+n+1);if(tot==0) mi=0;elsewhile(1){if(wo==0){if(mi>r-l) mi=r-l;l++;z=ff(1,n,y[l]);if(z!=0) {b[z]--;if(b[z]==0) wo++;}}else {if(r==m) break;r++;z=ff(1,n,y[r]);if(z!=0) {b[z]++;if(b[z]==1) wo--;}}}printf("%d\n",mi);return 0; }

?

轉載于:https://www.cnblogs.com/huihao/p/7128694.html

總結

以上是生活随笔為你收集整理的【洛谷P1381】单词背诵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。