当前位置:网站首页>字典树简单入门题(居然是蓝题?)
字典树简单入门题(居然是蓝题?)
2022-07-05 20:54:00 【汤键.TJ】
[TJOI2010] 阅读理解
题目描述
英语老师留了 N N N 篇阅读理解作业,但是每篇英文短文都有很多生词需要查字典,为了节约时间,现在要做个统计,算一算某些生词都在哪几篇短文中出现过。
输入格式
第一行为整数 N N N ,表示短文篇数,其中每篇短文只含空格和小写字母。
按下来的 N N N 行,每行描述一篇短文。每行的开头是一个整数 L L L ,表示这篇短文由 L L L 个单词组成。
接下来是 L L L 个单词,单词之间用一个空格分隔。
然后为一个整数 M M M ,表示要做几次询问。后面有 M M M 行,每行表示一个要统计的生词。
输出格式
对于每个生词输出一行,统计其在哪几篇短文中出现过,并按从小到大输出短文的序号,序号不应有重复,序号之间用一个空格隔开(注意第一个序号的前面和最后一个序号的后面不应有空格)。如果该单词一直没出现过,则输出一个空行。
样例 #1
样例输入 #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 % 30\% 30% 的数据, 1 ≤ M ≤ 1 0 3 1\le M\le 10^3 1≤M≤103 。
对于 100 % 100\% 100% 的数据, 1 ≤ M ≤ 1 0 4 1\le M\le 10^4 1≤M≤104, 1 ≤ N ≤ 1 0 3 1\le N\le 10^3 1≤N≤103 。
每篇短文长度(含相邻单词之间的空格) ≤ 5 × 1 0 3 \le 5\times 10^3 ≤5×103 字符,每个单词长度 ≤ 20 \le 20 ≤20 字符。
每个测试点时限 2 2 2 秒。
所有过程都在注释里
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long ll;
int son[N][30],idx,n,l,m;
char a[N];
bitset<1010> sign[N];
// 用bool会爆空间
// 用bool一个值占1字节,1个字节是8比特
// 用bitset则每个bool值只占用一个比特,大大节省空间
void insert(char str[],int k){
//插入字符串,同时告知是哪行
int p=0; //从根节点开始遍历插入
int l=strlen(str);
for(int i=0;i<l;i++){
int u=str[i]-'a'; // 方便当作下标
if(!son[p][u]) son[p][u]=++idx;
//查看当前节点p的子节点u是否已给予编号,没有则标记给予编号
p=son[p][u];//移至下一节点转换位置
}
sign[p][k]=1;//标记该字符串存在于第k行
}
void find(char str[]){
//查找该字符串
int p=0,signsign=1;//初始化,回到根节点继续查
int l=strlen(str);
for(int i=0;i<l;i++){
//遍历节点进行查询
int u=str[i]-'a';
if(!son[p][u]){
//一旦发现未被标记,则不存在该字符串,退出遍历查询
signsign=0;//同时标记不存在
break;
}
p=son[p][u];//移至下一节点转换位置
}
if(signsign){
//通过标记判断是否查询成功
for(int i=1;i<=n;i++){
if(sign[p][i]){
//通过标记查看此行是否存在此字符串
printf("%d ",i);
}
}printf("\n");
}
else{
puts("");
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>l;
for(int j=1;j<=l;j++){
scanf("%s",a);
insert(a,i);
}
}
cin>>m;
for(int i=1;i<=m;i++){
scanf("%s",a);
find(a);
}
return 0;
}
边栏推荐
- 清除app data以及获取图标
- ProSci LAG3抗体的化学性质和应用说明
- Abnova丨DNA 标记高质量控制测试方案
- shell编程100例
- Promouvoir le développement de l'industrie culturelle et touristique par la recherche, l'apprentissage et l'enseignement pratique du tourisme
- Duchefa细胞分裂素丨二氢玉米素 (DHZ)说明书
- phpstudy小皮的mysql点击启动后迅速闪退,已解决
- PHP deserialization +md5 collision
- mysql全面解析json/数组
- wpf 获取datagrid 中指定行列的DataGridTemplateColumn中的控件
猜你喜欢
教你自己训练的pytorch模型转caffe(二)
Promouvoir le développement de l'industrie culturelle et touristique par la recherche, l'apprentissage et l'enseignement pratique du tourisme
解析五育融合之下的steam教育模式
Make Jar, Not War
Abnova丨荧光染料 620-M 链霉亲和素方案
Abnova丨E (DIII) (WNV) 重组蛋白 中英文说明书
请查收.NET MAUI 的最新学习资源
当Steam教育进入个性化信息技术课程
Abnova丨 MaxPab 小鼠源多克隆抗体解决方案
Abnova丨培养细胞总 RNA 纯化试剂盒中英文说明书
随机推荐
Is it necessary for bazel to learn
phpstudy小皮的mysql点击启动后迅速闪退,已解决
解读协作型机器人的日常应用功能
解析创客教育的知识迁移和分享精神
实现浏览页面时校验用户是否已经完成登录的功能
培养机器人教育创造力的前沿科技
[quick start of Digital IC Verification] 2. Through an example of SOC project, understand the architecture of SOC and explore the design process of digital system
php中explode函数存在的陷阱
Abnova丨血液总核酸纯化试剂盒预装相关说明书
最长摆动序列[贪心练习]
How to make ERP inventory accounts of chemical enterprises more accurate
Maker education infiltrating the transformation of maker spirit and culture
Abnova fluorescent dye 620-m streptavidin scheme
ClickHouse 复制粘贴多行sql语句报错
Implementation of redis unique ID generator
产品好不好,谁说了算?Sonar提出分析的性能指标,帮助您轻松判断产品性能及表现
Web Service简单入门示例
Clear app data and get Icon
ts 之 泛型
Learning notes of SAS programming and data mining business case 19