洛谷 P3879 [TJOI2010]【阅读理解】

题目描述

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

输入输出格式

输入格式：

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

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

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

输出格式：

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

输入输出样例

输入样例#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：

解题思路

　　首先就是字典树了，只是我们定一个bool数组判断某个单词是否在某篇文章出现过，然后.........最后一个点就WA了（当时我也蒙了）原来，我们定义bool数组可以换成bitset，这样时间复杂度可以/32，非常实用，强烈安利。

题解

 1 #include<bits/stdc++.h>
 2 #define N 300001
 3 using namespace std;
 4 int n,m,l; 
 5 char x[10001];
 6 struct Trie{
 7     int sz;
 8     int ch[N][26];
 9     bitset<1001>val[N];//bitset 
10     Trie(){
11         sz=1;
12         memset(ch[0],0,sizeof(ch[0]));
13         memset(val,0,sizeof(val));
14     }//初始化 
15     int idx(char c)//字符转数字 
16     {
17         return c-'a';
18     }
19     void insert(string s,int num)//插入 
20     {
21         int u=0;
22         for(int i=0;i<s.size();i++)
23         {
24             int c=idx(s[i]);
25             if(!ch[u][c])
26             {
27                 memset(ch[sz],0,sizeof(ch[sz]));
28                 ch[u][c]=sz;
29                 sz++;
30             }
31             u=ch[u][c];//向下便利 
32         }
33         val[u][num]=1;//在第num篇文章出现过 
34     }
35     void find(string s)//查找 
36     {
37         int u=0;
38         for(int i=0;i<s.size();i++)
39         {
40             int c=idx(s[i]);
41             if(!ch[u][c])//没找到了 
42             {
43                 cout<<endl;
44                 return;
45             }
46             u=ch[u][c];
47         }
48         for(int i=1;i<=n;i++)//看在哪几篇文章出现过 
49         {
50             if(val[u][i]==1)cout<<i<<" ";
51         }
52         cout<<endl;
53     }
54 }tree;
55 int main()
56 {
57     scanf("%d",&n);
58     for(int i=1;i<=n;i++)
59     {
60         cin>>l;
61         for(int j=1;j<=l;j++)
62         {
63             scanf("%s",x);
64             tree.insert(x,i);
65         }
66     }
67     scanf("%d",&m);
68     for(int i=1;i<=m;i++)
69     {
70         scanf("%s",x);
71         tree.find(x);
72     }
73     return 0;
74 }