洛谷P3879《[TJOI2010]阅读理解》

十二月 26, 2018 3485

实在是一道练习 std::map 的好题啊

题目链接

题目描述

英语老师留了N篇阅读理解作业，但是每篇英文短文都有很多生词需要查字典，为了节约时间，现在要做个统计，算一算某些生词都在哪几篇短文中出现过。

输入输出格式

输入格式

第一行为整数 N ，表示短文篇数，其中每篇短文只含空格和小写字母。

按下来的 N 行，每行描述一篇短文。每行的开头是一个整数 L ，表示这篇短文由 L 个单词组成。接下来是 L 个单词，单词之间用一个空格分隔。

然后为一个整数 M ，表示要做几次询问。后面有 M 行，每行表示一个要统计的生词。

输出格式

对于每个生词输出一行，统计其在哪几篇短文中出现过，并按从小到大输出短文的序号，序号不应有重复，序号之间用一个空格隔开（注意第一个序号的前面和最后一个序号的后面不应有空格）。如果该单词一直没出现过，则输出一个空行。

输入输出样例

输入样例

1
2
3
4
5
6
7
8
9
10
3
9 you are a good boy ha ha o yeah
13 o my god you like bleach naruto one piece and so do i
11 but i do not think you will get all the points
5
you
i
o
all
naruto

输出样例

1
2
3
4
5
6
1 2 3
2 3
1 2
3
2

其他说明

对于30%的数据，1 ≤ M ≤ 1,000

对于100%的数据，1 ≤ M ≤ 10,000，1 ≤ N ≤ 1000

每篇短文长度（含相邻单词之间的空格） ≤ 5,000 字符，每个单词长度 ≤ 20 字符

解题思路

Trie？Hash？KMP？Aho-Corasick Automaton？

统统不要！

这可是练习 std::map 的一道好题啊！

我们考虑开一个 std::map<std::string, std::vector<int> >，其中下标为每个单词，元素为这个单词对应在哪几个句子中出现过（所以要用 std::vector<int> 啊）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    std::map<std::string, std::vector<int> > mp;
    
    int n, m;
    std::string s;
}

signed main() {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    std::ios::sync_with_stdio(false);
    using std::cin;
    using std::cout;
    using std::endl;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int p;
        cin >> p;
        for (int j = 1; j <= p; ++j) {
            cin >> s;
            mp[s].push_back(i); // 记录当前单词在哪几个句子里出现过
        }
    }
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> s;
        int siz = (int) mp[s].size();
        for (int j = 0; j < siz; ++j) {
            if (j != 0 && mp[s][j] == mp[s][j-1]) continue; // 手动去重
            cout << mp[s][j]; // 输出
            if (j != siz - 1) cout << ' '; // 输出行中空格
        }
        cout << endl; // 输出回车键
    }
    return 0;
}