[TJOI2010] 阅读理解

题意

给出 n 篇文章的单词。每次查询一个单词，按升序输出它出现过的文章编号；同一文章重复出现只输出一次编号，不存在则输出空行。

思路

两种做法，模型完全一样：单词 → 文章编号列表。

Python 字典

查询方向是"由单词找文章"（给定一个词，问在哪几篇里出现过）。自然的做法是预处理一个倒排索引：

正排（文章→单词）：第 1 篇文章有单词 {a, b, c}，第 2 篇有 {b, d}…… 倒排（单词→文章）：单词 a 出现在 {1}，b 出现在 {1, 2}，c 出现在 {1}，d 出现在 {2}……

“倒排"就是把映射方向反过来——不是"这篇文章有什么词”，而是"这个词在哪几篇文章里"：

text

1单词 -> 出现过的文章编号列表

读第 article_id 篇文章时，先用 set 对该篇单词去重，再把编号追加到每个单词的列表。文章按 1..n 顺序处理，所以列表天然递增，不需要额外排序。

查询时直接取得对应列表。defaultdict(list) 对未出现的单词自动给出空列表，连接后自然得到题目要求的空行。

C++ 字典树（Trie）

对于 C++，用字典树统一管理字符串，每个节点存储它代表的单词出现在哪些文章中。

插入时沿着单词往下走，走到结尾节点后把当前文章编号加入 belong 列表。由于同一篇文章的同一个词可能多次出现，文章编号按 1..n 顺序插入，只需检查列表尾部是否相同即可去重。

查询时沿 Trie 找到结尾节点，输出其 belong 列表；找不到时输出空行。

Python 知识

defaultdict(list) 省去“键不存在就先建立空列表”的分支。
set(words) 只去掉同一篇文章内的重复，不影响文章编号顺序。
articles[word].append(article_id) 是典型的一对多索引写法。
生成器表达式按查询顺序生成每一行答案，再统一用换行连接。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：defaultdict、集合和一对多映射。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：生成器式批量输出。

代码

Python（字典 + 倒排索引）：

python

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
35import sys
from collections import defaultdict


def main():
    # 一次性读入所有输入，按空白字符分割
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    pos = 1
    articles = defaultdict(list)  # 倒排索引：单词 → 文章编号列表

    # 读入 n 篇文章
    for article_id in range(1, n + 1):
        word_count = int(data[pos])
        pos += 1
        # 每篇文章内用 set 去重，避免同一文章重复编号
        words = set(data[pos:pos + word_count])
        pos += word_count
        # 把当前文章编号加入每个单词的列表
        for word in words:
            articles[word].append(article_id)

    # 读入询问
    query_count = int(data[pos])
    pos += 1
    # 生成器依次处理每个询问：找到列表就直接输出，找不到就输出空串
    answer = (
        " ".join(map(str, articles[word]))
        for word in data[pos:pos + query_count]
    )
    print("\n".join(answer))


if __name__ == "__main__":
    main()

C++（字典树）：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXNODE = 500005;

int trie[MAXNODE][26];
int node_cnt = 1; // 1 号点作为根

vector<int> belong[MAXNODE]; // belong[p] 记录单词 s 出现在了哪些文章里

int get_new_node() {
    ++node_cnt;
    return node_cnt;
}

// 把一个单词插入字典树，并把它出现的文章编号 article 记到结尾节点。
void insert_word(const string &s, int article) {
    int p = 1;
    for (int i = 0; i < (int) s.size(); i++) {
        int ch = s[i] - 'a';
        if (trie[p][ch] == 0) {
            trie[p][ch] = get_new_node();
        }
        p = trie[p][ch]; // p 成为当前前缀的唯一节点编号
    }

    if (belong[p].empty() || belong[p].back() != article) {
        belong[p].push_back(article);
    }
}

int find_word(const string &s) {
    int p = 1;
    for (int i = 0; i < (int) s.size(); i++) {
        int ch = s[i] - 'a';
        if (trie[p][ch] == 0) {
            return 0; // 路径断开，单词不在 Trie 中
        }
        p = trie[p][ch]; // p 成为当前前缀的唯一节点编号
    }
    return p;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int cnt;
        cin >> cnt;
        for (int j = 1; j <= cnt; j++) {
            string s;
            cin >> s;
            insert_word(s, i);
        }
    }

    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        string s;
        cin >> s;
        int p = find_word(s);

        if (p == 0 || belong[p].empty()) {
            cout << '\n';
            continue;
        }

        for (int j = 0; j < (int) belong[p].size(); j++) {
            if (j > 0) {
                cout << ' ';
            }
            cout << belong[p][j];
        }
        cout << '\n';
    }

    return 0;
}

复杂度

设所有输入和查询单词的总字符数为 $L$ 。

做法	时间	空间
Python dict	$O(L)$ 期望	$O(L)$
C++ Trie	$O(L)$	$O(L \times 26)$ 节点数

总结

Python 字典直接把完整单词映射到文章列表，既精确又简洁；每篇先去重是避免重复文章编号的关键。C++ 用 Trie 做同样的事，优势在字符串前缀共享和稳定的时间表现。