题意描述 英语老师留了$N$篇阅读理解作业,但是每篇英文短文都有很多生词需要查字典。
为了节约时间,现在需要你来做个统计,算一算某些生词都在哪几篇短文中出现过。
输入格式 第一行为整数$N$,表示短文篇数,其中每篇短文只含空格和小写字母。
按下来的$N$行,每行描述一篇短文。每行的开头是一个整数$L$,表示这篇短文由$L$个单词组成。接下来是$L$个单词,单词之间用一个空格分隔。
然后为一个整数$M$,表示要做$M$次询问。后面有$M$行,每行表示一个要统计的生词。
输出格式 输出$M$行,分别表示每个生词在哪几篇短文中出现过。并按从小到大输出短文的序号。序号之间用一个空格隔开
如果该单词一直没出现过,则仅输出一个空行即可。
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
Output ‘s eg
数据范围和约定 对于$30\%$的数据,$1 ≤ M ≤ 10^3$
对于$100\%$的数据,$1 ≤ M ≤ 10^5,1 ≤ N ≤ 10^3$
每篇短文长度(含相邻单词之间的空格) $≤ 5,000$个字符,每个单词长度 $≤ 20$个字符
分析 又是一道Trie
树的模板
对于每篇文章,我们把它的每一个单词插入Trie
树之中,之后用bool
数组$flag[rt][i]$表示$rt$在第$i$篇文章中是否出现过。
查询时从小到大遍历每一篇文章(即$flag$数组的第二维),如果被标记过,输出即可。
最后别忘了输出空行。
$Upd$:后来有个老鸽传了一组数据,在空间上卡掉了用来判断是否出现的$flag$数组。针对这种做法,我们可以将其开为bitset
。
这样的话,$flag$数组的空间大小就变成了原来的$\frac{1}{32}$,即可轻松通过本题。
以及,bitset
使用之前需要添加#include<bitset>
Code[Accepted] #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <stack> #include <queue> #include <deque> #include <vector> #include <algorithm> #include <iomanip> #include <cstdlib> #include <cctype> #include <cmath> #include <bitset> #define ll long long #define I inline #define N 500001 using namespace std ;int n , m , k;bitset <1001> flag[N];namespace Trie{ struct Node { int son[26 ]; }node[N]; int tot = 0 ; void insert (int x , string s) { int len = s.length() , rt = 0 ; for (int i = 0 ; i < len; i ++){ int c = s[i] - 'a' ; if (!node[rt].son[c]){ node[rt].son[c] = ++ tot; } rt = node[rt].son[c]; } flag[rt][x] = true ; } void find (string s) { bool bj = true ; int len = s.length() , rt = 0 ; for (int i = 0 ; i < len; i ++){ int c = s[i] - 'a' ; if (!node[rt].son[c]){ bj = false ; break ; } rt = node[rt].son[c]; } if (bj == true ){ for (int i = 1 ; i <= n; i ++){ if (flag[rt][i]){ cout << i << " " ; } } } cout << "\n" ; } } int main () { string str; cin >> n; for (int i = 1 ; i <= n; i ++){ cin >> m; for (int j = 1 ; j <= m; j ++){ cin >> str; Trie :: insert(i , str); } } cin >> k; for (int i = 1 ; i <= k; i ++){ cin >> str; Trie :: find(str); } return 0 ; }
THE END