题解 P1381 【单词背诵】

· · 题解

首先记录在文章中出现了多少个要背的单词

我们可以用map方便地记录某个单词是否是要背的单词/是否被记录过

用vis记录某个单词是否是要背的单词，vi记录这个单词是否已经被记录过，从而求出文章中要背的单词个数num

然后枚举文章中出现的每一个单词，用cnt记录段落中有多少个要背的单词，用v记录每个单词在段落中出现了多少次，用head记录段落开头的位置

如果在head位置的单词不需要背/在段落中出现过两次以上，就让head前移一位

如果段落中要背的单词数目等于num，就每次取最小长度作为答案

蒟蒻语文不好，请结合代码理解~

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
string a[100003];
map<string,int> v;
map<string,bool> vis,vi;
int n,m,head=1,cnt,num;
int ans=2147483647;
int main()
{
    scanf("%d",&n);
    string s;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        vis[s]=true;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        cin>>s;
        a[i]=s;
        if(vis[s]&&!vi[s])
        //要背且之前没有记录
        {
            vi[s]=true;
            num++;
        }
    }
    printf("%d\n",num);
    for(int i=1;i<=m;i++)
    {
        s=a[i];
        if(!vis[s]) continue;
        //不需要背就continue
        if(!v[s]) cnt++;
        //之前没出现过cnt就+1
        v[s]++;//出现次数+1
        while(!vis[a[head]]||(head<i&&v[a[head]]>1))
        //不需要背或者出现过一次以上
        {
            v[a[head]]--;
            head++;
        }
        if(cnt==num) ans=min(ans,i-head+1);
    }
    if(ans!=2147483647) printf("%d",ans);
    else printf("0");
    //一定要特判！不然会WA掉一个点
    return 0;
}

如果有更好的做法，欢迎提出~