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：

说明

对于30%的数据，1 ≤ M ≤ 1,000

对于100%的数据，1 ≤ M ≤ 10,000，1 ≤ N ≤ 1000

每篇短文长度（含相邻单词之间的空格） ≤ 5,000 字符，每个单词长度 ≤ 20 字符

每个测试点时限2秒

感谢@钟梓俊添加的一组数据

害怕MLE数组都没敢开。。。

#include<map>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

map<string,int>ma[];

int n,m;

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        int x;scanf("%d",&x);

        for(int j=;j<=x;j++){

            string x;cin>>x;

            ma[i][x]=;

        }

    }

    scanf("%d",&m);

    for(int i=;i<=m;i++){

        string p;cin>>p;

        for(int j=;j<=n;j++)

            if(ma[j][p])

                cout<<j<<" ";

        cout<<endl;

    }

}

90暴力

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,tot;

int tree[][];

bool ans[][];

int read(){

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void insert(string s,int now){

    int root=;

    int len=s.length();

    for(int i=;i<len;i++){

        int x=s[i]-'a';

        if(!tree[root][x])    tree[root][x]=++tot;

        root=tree[root][x];

    }

    ans[root][now]=;

}

void find(string s){

    int root=;

    int len=s.length();

    for(int i=;i<len;i++){

        int x=s[i]-'a';

        if(!tree[root][x]){ puts("");return ;}

        root=tree[root][x];

    }

    for(int i=;i<=n;i++)

        if(ans[root][i])

            printf("%d ",i);

    puts("");

    return ;

}

int main(){

    n=read();

    for(int i=;i<=n;i++){

        int x;x=read();

        for(int j=;j<=x;j++){

            string p;cin>>p;

            insert(p,i);

        }

    }

    m=read();

    for(int i=;i<=m;i++){

        string p;cin>>p;

        find(p);

    }

}

trie树

阅读理解

洛谷 P3879 [TJOI2010]阅读理解

P3879 [TJOI2010]阅读理解

题目描述

输入输出格式

输入输出样例

说明