codevs 3013 单词背诵 hash

题目链接

题目描述 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

第一问很好求，用map统计就可以了，第二问用双指针的思想。 r一直向右移动，当map里的个数和第一问求出来的cnt相同的时候，移动左指针直到刚刚好满足要求。ans= min(ans, r-l），然后一直这样找下去直到r==m。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

map <string, int> mp1, mp2;

string a[];

int main()

{

    int n, m, cnt = , tot = ;

    string s;

    cin>>n;

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

        cin>>s;

        mp1[s] = ;

    }

    cin>>m;

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

        cin>>a[i];

        if(mp1[a[i]]&&!mp2[a[i]]) {

            cnt++;

            mp2[a[i]] = ;

        }

    }

    mp2.clear();

    cout<<cnt<<endl;

    int r = , l = , ans = inf;

    while(r<m) {

        while(r<m) {

            if(!mp1[a[r]]) {

                r++;

                continue;

            }

            if(!mp2[a[r]]) {

                tot++;

            }

            mp2[a[r]]++;

            r++;

            if(tot == cnt)

                break;

        }

        while(l<r && (!mp2[a[l]] || mp2[a[l]]>)) {

            if(mp2[a[l]])

                mp2[a[l]]--;

            l++;

        }

        ans = min(ans, r-l);

    }

    cout<<ans<<endl;

    return ;

}

秒客网

codevs 3013 单词背诵 hash

相关文章