CODEVS——T 3013 单词背诵

http://codevs.cn/problem/3013/

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题解

查看运行结果

题目描述 Description

灵梦有n个单词想要背，但她想通过一篇文章中的一段来记住这些单词。

文章由m个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样她就可以用尽量短的时间学习尽可能多的单词了。

输入描述 Input Description

第1行一个数n，

接下来n行每行是一个长度不超过10的字符串，表示一个要背的单词。

接着是一个数m，

然后是m行长度不超过10的字符串，每个表示文章中的一个单词。

输出描述 Output Description

输出文件共2行。第1行为文章中最多包含的要背的单词数，第2行表示在文章中包含最多要背单词的最短的连续段的长度。

样例输入 Sample Input

hot

dog

milk

hot

dog

milk

hot

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于30%的数据 n<=50，m<=500；

对于60%的数据 n<=300，m<=5000；

对于100%的数据 n<=1000，m<=100000；

第一问：用Hash得到需要的单词在文章中出现的情况

第二问：想从文章开始就将单词入队，保证需要背的都在队内，然后开始缩短长度

若队头不是需要单词或者在队内的次数多余1，则将其删除

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 #define p 19

 #define mod 100007

 const int N(+);

 char s1[N][],s2[N][];

 int ans,n,m,num[N],need[N],vis[N],have[N];

 int Hash(char a[])

 {

     int ret=;

     for(int i=;i<strlen(a);i++)

         ret=(ret*p+a[i]-'a')%mod;

     return ret;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%s",s1[i]);

     scanf("%d",&m); int len=m;

     for(int i=;i<=m;i++)

         scanf("%s",s2[i]),have[Hash(s2[i])]=;

     for(int i=;i<=n;i++)

     {

         int ha=Hash(s1[i]);

         if(have[ha]) ans++,need[ha]=;

     }

     for(int cnt=,head=,tail=;tail<=m;)

     {

         int ha=Hash(s2[++tail]);

         if(need[ha])

         {

             if(!vis[ha]) cnt++;

             num[ha]++; vis[ha]=;

         }

         if(cnt==ans&&ans)

         {

             int x=Hash(s2[head]);

             for(;head<tail&&(num[x]>||!need[x]);)

             {

                 if(need[x]) num[x]--;

                 x=Hash(s2[++head]);

             }

             len=min(len,tail-head+);

         }

     }

     if(!ans) printf("0\n0");

     else printf("%d\n%d",ans,len);

     return ;

 }

巴特西

CODEVS——T 3013 单词背诵

http://codevs.cn/problem/3013/

最新文章

热门文章