题解 P3879 【[TJOI2010]阅读理解】

Qglin_ · 2019-01-26 18:55:31 · 题解

简单地读题可知，这是一道非常简单的Trie树板子题。

那我们也不考虑这么多了，直接暴力一点吧。

观察到每篇短文长度\le5000，N\le1000，M\le10000

那么我们直接维护1000个5000节点的Trie树，每个Trie树存储一段短文，每次查询就从头枚举一遍每一篇短文，按照题目找到答案就输出，然后换行，在这个数据强度下是可以通过此题的。

贴代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

inline int fd() {//快读
    int x = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -f; ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

struct trie {
    struct node {
        int son[26];
        bool fin;
    } nd[5010];
    int sum;
    void insert(char *s) {
        int v, len = strlen(s), u = 0;
        for(int i = 0; i < len; ++i) {
            v = s[i]-'a';
            if(!nd[u].son[v]) nd[u].son[v] = ++sum;
            u = nd[u].son[v];
        }
        nd[u].fin = 1;
    }
    bool tfind(char *s) {
        int u = 0, v, len = strlen(s);
        for(int i = 0; i < len; ++i) {
            v = s[i]-'a';
            if(!nd[u].son[v]) return false;
            u = nd[u].son[v];
        }
        if(nd[u].fin) return true;
        return false;
    }
}T[1005];//结构体封装1005个Trie树，多开一点保险

char s[5005];//用来输入
int n, m;

int main() {
    n = fd();
    for(int i = 1; i <= n; ++i) {/*按照每行输入的格式处理，输入一个单词并将它插入对应短文编号的Trie树*/
        m = fd();
        for(int j = 1; j <= m; ++j) {
            scanf("%s",s);
            T[i].insert(s);
        }
    }
    m = fd();
    for(int i = 1; i <= m; ++i) {
        scanf("%s",s);
        for(int j = 1; j <= n; ++j) {
            if(T[j].tfind(s)) printf("%d ",j);/*查找单词，如果找到了就输出当前短文编号*/
        }
        putchar('\n');
    }
    return 0;//完美结束
}

果然暴力做法是这个世界上最美的做法