Trie树【洛谷P3879】 [TJOI2010]阅读理解
2024-09-01 07:31:20
P3879 [TJOI2010]阅读理解
题目描述
英语老师留了N篇阅读理解作业,但是每篇英文短文都有很多生词需要查字典,为了节约时间,现在要做个统计,算一算某些生词都在哪几篇短文中出现过。
输入输出格式
输入格式:
第一行为整数N,表示短文篇数,其中每篇短文只含空格和小写字母。
按下来的N行,每行描述一篇短文。每行的开头是一个整数L,表示这篇短文由L个单词组成。接下来是L个单词,单词之间用一个空格分隔。
然后为一个整数M,表示要做几次询问。后面有M行,每行表示一个要统计的生词。
输出格式:
对于每个生词输出一行,统计其在哪几篇短文中出现过,并按从小到大输出短文的序号,序号不应有重复,序号之间用一个空格隔开(注意第一个序号的前面和最后一个序号的后面不应有空格)。如果该单词一直没出现过,则输出一个空行。
卡空间的毒瘤题。
怒开bitset过掉。
code:
#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
const int wx=500017;
inline int read(){
int sum=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}
return sum*f;
}
int n,m;
char c[wx];
struct Trie{
int tr[wx][29];
bitset<1010>flag[wx];
int cnt;
void insert(char *s,int fl){
int p=0;
for(int i=0;s[i];i++){
int k=s[i]-'a';
if(!tr[p][k])tr[p][k]=++cnt;
p=tr[p][k];
}
flag[p][fl]=1;
}
void query(char *s){
int p=0;
for(int i=0;s[i];i++){
int k=s[i]-'a';
if(!tr[p][k]){
puts("");
return ;
}
p=tr[p][k];
}
for(int i=1;i<=n;i++){
if(flag[p][i])printf("%d ",i);
}puts("");
}
}Trie;
int main(){
n=read();
for(int i=1;i<=n;i++){
int x; x=read();
for(int j=1;j<=x;j++){
scanf("%s",c);
Trie.insert(c,i);
}
}
m=read();
for(int i=1;i<=m;i++){
scanf("%s",c);
Trie.query(c);
}
return 0;
}
最新文章
- HTML和CSS设置动态导航以及CSS中伪元素的简单说明
- 使用git的分支功能实现定制功能摘取与组合的想法
- HDU-4518 吉哥系列故事——最终数 AC自动机+数位DP
- Linux Watchdog Test Program
- jquery ui dialog去除第一个文本框焦点问题
- CoreAnimation4-隐式动画和显式动画
- hadoop笔记之Hive的管理(web界面方式)
- golang实现udp接入服务器
- Holding Bin-Laden Captive!(1.多重背包 2.母函数)
- 一个RtspServer的设计与实现和RTSP2.0简介
- DDD - 概述 - 聚合 (三)
- MyEclipse配置tomcat报错 - java.lang.UnsupportedClassVersionError: org/apache/lucene/store/Directory : Unsupported major.minor version 51.0
- python3.x与2.x区别
- php实现概率性随机抽奖代码
- java String 中替换";\";为";\\";
- java 生成jar包并保留注释
- Android Camera开发:给摄像头预览界面加个ZoomBar(附完整代码下载)
- kali&;BT安装好之后无法上网(包括Wifi)或者无法获得内网IP解决方法
- vc libcurl 模拟上传文件
- LinkedList的一种错误使用方法