题解 | #阅读理解#

题目描述

英语老师布置了 篇阅读理解作业。对于若干给定的生词，老师想知道它们分别出现在了哪些短文中，以便统计查词量。

给定 篇短文与 次查询，每次给出一个单词 ，请输出 出现过的所有短文编号（按升序），若从未出现则输出空行。

本题是哈希表赢麻了的题

核心思路

核心观察

• 每篇短文可视为一个单词集合（因为同一单词在同一篇中重复出现只需记录一次）。
• 查询要求：对每个单词 ，快速找出它出现在哪些文章中。
• 由于 、每篇文章最多 50 个单词、总单词种类有限，可以预处理：为每篇文章建立一个哈希集合（unordered_set），用于快速判断某单词是否在该文中出现。
• 查询时，遍历所有文章编号 到 ，检查当前单词是否在第 篇的集合中。由于题目要求按升序输出，而我们正是从小到大遍历，天然满足顺序。

注意：不能反向建索引（如 map<string, vector<int>>）虽然更高效，但本题数据规模小，直接遍历完全可接受，且代码简洁。

算法步骤

1. 读入 。
2. 对每篇短文 到 ：
   • 读入单词数量 。
   • 读入 个单词，插入到 v[i]（unordered_set<string>）中。
3. 读入查询次数 。
4. 对每个查询单词 ：
   • 遍历 到 ：
     • 若 v[i].count(w) == 1，输出 i 并加空格。
   • 输出换行（即使无结果，也输出空行）。

正确性分析

• 使用 unordered_set 可以在平均 时间内判断单词是否存在。
• 遍历文章编号从 1 到 ，保证输出编号严格升序。
• 每次查询独立处理，互不影响。
• 空行处理：若没有任何文章包含该词，则循环中不输出任何数字，直接 cout << endl; 即为空行，符合要求。

复杂度分析

• 时间复杂度：
  • 预处理：
  • 查询：，在 C++ 中可接受。
• 空间复杂度：，存储所有单词。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n;cin>>n;
    vector<unordered_set<string>>v(n+1);
    for(int i=1;i<=n;i++){//从1开始存入
        int tem;cin>>tem;
        v[i].reserve(tem);//重设哈希表大小避免多次申请大内存
        for(int j=0;j<tem;j++){
            string s;cin>>s;
            v[i].insert(s);
        }
    }
    int q;cin>>q;
    while(q--){
        string s;
        cin>>s;
        for(int i=1;i<=n;i++){
            if(v[i].count(s)){//统一API，count就是查找返回bool
                cout<<i<<" ";
            }
        }
        cout<<endl;
    }
}