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: 复制
1 2 3
2 3
1 2
3
2
说明
对于30%的数据,1 ≤ M ≤ 1,000
对于100%的数据,1 ≤ M ≤ 10,000,1 ≤ N ≤ 1000
每篇短文长度(含相邻单词之间的空格) ≤ 5,000 字符,每个单词长度 ≤ 20 字符
每个测试点时限2秒
这个题也是一个字典树的题目,但是这个题目好像是没有卡STL的,所以用STL也能过。
这个题用字典树写的话 数组开小了会WA#11,数组开大了前面就会有几组数据MLE
通过了解 用 bitset 可以节省空间,把bool型的数改成 bitset就可以过了
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int t,n,m,tree[maxn][30],cnt;
bitset<1001> vis[maxn];
string x;
void insert(string s,int rt,int y)//一个个单词的插入 y表示在第几行句子中
{
int q=s.length();
for(int i=0; i<q; i++)
{
int x=s[i]-'a';
if(tree[rt][x]==0) tree[rt][x]=++cnt;
rt=tree[rt][x];
}
vis[rt][y]=1;//标记
}
void find(string s,int rt)
{
int q=s.length();
for(int i=0; i<q; i++)
{
int x=s[i]-'a';
if(tree[rt][x]==0)
{
cout<<" "<<endl;//不存在则输出空行
return ;
}
rt=tree[rt][x];
}
int flag=0;
for(int i=1; i<=t; i++)//输出
{
if(flag==0&&vis[rt][i]==1)
{
flag=1;
cout<<i;
}
else if(vis[rt][i]==1)
{
cout<<" "<<i;
}
}
cout<<endl;
return;
}
int main()
{
cin>>t;
for(int i=1; i<=t; i++)
{
cin>>n;
while(n--)
{
cin>>x;
insert(x,0,i);
}
}
cin>>m;
while(m--)
{
cin>>x;
find(x,0);
}
return 0;
}