1. 题目

传送们= ̄ω ̄=

2. 题解

首先搞个set哈希一下存在的单词,对于文章中不存在的单词直接跳过就行了。
最普通的做法是枚举文章起点、终点,判断是否合法。然而会超时。
我们现在只枚举文章终点,我们需要均摊O(1)地获取文章起点。
起点需要满足什么条件呢?
首先,需要包含最多的要背的单词。
其次,越靠近终点越好。
我们可以考虑递推。
这一次相比于上一次终点加了1,获取了一个新的文章中的单词,这个单词说不定之前就在文章中出现过,而且在目前的起点到终点之间,所以我们要把上一次出现的给排除掉,说不定排除掉以后起点就可以向终点推进了。
比如对于样例:

3
hot
dog
milk
5
hot
dog
dog
milk
hot

设起点为top,终点为end
1. top=1,end=1,文章为:hot,答案=1
2. top=1,end=2,文章为:hot,dog,答案=2(因为获取了新的单词,所以虽然答案变大了但是也要改变)
3. top=1,end=3,因为文章中有dog了,所以清除上一个dog,文章为:hot,(空),dog,答案=min(2,3)=2
4. top=1,end=4,文章为:hot,(空),dog,milk,答案=4(因为获取了新的单词,所以虽然答案变大了但是也要改变)
5. top=1,end=5,因为文章中有hot了,所以清除上一个hot,文章为:(空),(空),dog,milk,hot,因为前两个(top,top+1)文章中的单词都变为空了,所以没必要选一段为空的单词,所以top=3(第一个不为空的单词的位置),文章变为了:dog,milk,hot,这时候答案=min(4,3)=3,所以答案=3

所以只要:while(单词[top]==(空))top=top+1就可以保证top对于当前的end来说最优了,因为top最多移动n次,所以均摊O(1)

至于统计单词数。。。没啥好说的

代码:

#include <bits/stdc++.h>
using namespace std;
void SIN(string&s)
{
    char c=getchar();
    while(!isalpha(c))c=getchar();
    while(isalpha(c))s.push_back(c),c=getchar();
}
int n,m,top=1,ans=INT_MAX,cnt;
map<string,int> tab;
set<string> SET;
bool book[100005];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){string a;SIN(a),SET.insert(a);}
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        string a;SIN(a);
        if(SET.count(a)==0)continue;
        int k=tab[a];tab[a]=i,book[i]=1,book[k]=0;
        if(!k)ans=i-top+1,cnt++;
        while(!book[top])top++;
        ans=min(ans,i-top+1);
    }
    if(!cnt)ans=0;
    printf("%d\n%d\n",cnt,ans);
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *