阅读理解【牛客tracker 每日一题】

阅读理解

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

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

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

输入描述：

第一行输入整数N ( 1 ≦ N ≦ 10 3 ) N (1≦N≦10^3)N(1≦N≦103)。

接下来N NN行描述各短文，其中的第i ii行先给出整数L i ( 1 ≦ L i ≦ 50 ) L_i (1≦Li≦50)Li​(1≦Li≦50)——该短文包含的单词数量 ，随后L i L_iLi​个仅由小写英文字母组成的单词，每个单词长度不超过20 2020个字符，单词之间以单个空格分隔。

紧接着输入整数M ( 1 ≦ M ≦ 10 4 ) M (1≦M≦10^4)M(1≦M≦104)——查询次数。

之后M MM行，每行一个小写单词w j w_jwj​，表示一次查询。

输出描述：

对于每个查询单词w j w_jwj​：

• 若w j w_jwj​​ 出现过，输出其出现过的短文编号（ 1 ∼ N ） （1∼N）（1∼N），按升序用单个空格分隔；
• 若未出现，输出空行。

输出中每个查询对应一行，行首行尾均无多余空格。

示例1

输入：

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 2 3 1 2 3 2

解题思路

本题核心是通过哈希映射存储单词与短文编号的关联关系，选用map<string, set<ll>>作为核心容器，k e y keykey为单词字符串，v a l u e valuevalue为有序集合存储对应短文编号，集合可自动对短文编号去重且保持升序排列，完美匹配题目输出要求；先读取短文数量n nn，遍历每篇短文（编号1 ˜ n 1 \~\ n1˜n），读入单词数和对应单词，将单词与当前短文编号插入映射容器；再读取查询数m mm，逐次读入查询单词，遍历容器中该单词对应的集合，按序输出短文编号，无对应记录则输出空行。该方法利用容器特性省去手动去重和排序操作，结合数据规模（n ≤ 1 e 3 n≤1e3n≤1e3、单篇单词≤ 50 ≤50≤50、m ≤ 1 e 4 m≤1e4m≤1e4），时间复杂度高效且无冗余，精准完成所有查询的匹配与输出。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;intmain(){ll n;cin>>n;map<string,set<ll>>index;//构建哈希表（set为了去重）for(ll i=1;i<=n;i++){ll l;cin>>l;for(ll j=0;j<l;j++){string s;cin>>s;index[s].insert(i);}}ll m;cin>>m;for(ll j=0;j<m;j++){string w;cin>>w;for(ll i:index[w])cout<<i<<" ";cout<<endl;}return0;}