计蒜客劫富济贫 (Trie树)

**链接 : ** Here!

**思路 : ** Trie树裸题, 由开始给出的名字建一棵字典树, 然后每次查询一下抢♂劫的人名是否在字典树中, 复杂度也不清楚是多少, 反正是没给出 $M$ 的范围, 开始时用 $hash$ 做, $T$ 了, 分析一下也可以知道为什么 $T$, 因为对于不在富豪列表中的人, 还得跑一遍 $hash$ 函数, 这样的话每次就得执行 $strlen(NotRichName)$ 很浪费时间, 但是在 $Trie$ 树中直接 $1$ 次就能判定了, 所以对于这道题 $Trie树$ 不会 $T$.

/*************************************************************************

	> File Name: t22.cpp

	> Author:

	> Mail:

	> Created Time: 2017年11月24日 星期五 17时05分20秒

 ************************************************************************/

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAX_N = 1e8 + 2;

typedef long long ll;

const int SIZE = 30;

int n, m, x;

char str[MAX_N];

typedef struct TNode {

    int is_terminal;

    struct TNode **childs;

} TNode, *root;

TNode* new_node() {

    TNode *p = (TNode *)malloc(sizeof(TNode));

    p->childs = (TNode **)malloc(sizeof(TNode *) * SIZE);

    memset(p->childs, 0, sizeof(TNode *) * SIZE);

    p->is_terminal = -1;

    return p;

}

void clear(TNode *p) {

    if (!p) return;

    for (int i = 0 ; i < SIZE ; ++i) {

        clear(p->childs[i]);

    }

    free(p->childs);

    free(p);

}

void insert(TNode *node, char *pattern, int x) {

    TNode *p = node;

    for (int i = 0 ; pattern[i] ; ++i) {

        if (p->childs[pattern[i] - 'a'] == NULL) {

            p->childs[pattern[i] - 'a'] = new_node();

        }

        p = p->childs[pattern[i] - 'a'];

    }

    p->is_terminal = x;

}

int find(TNode *node, char *pattern) {

    TNode *p = node;

    for (int i = 0 ; pattern[i] ; ++i) {

        if (p->childs[pattern[i] - 'a'] == NULL) {

            return -1;

        }

        p = p->childs[pattern[i] - 'a'];

    }

    return p->is_terminal;

}

int main() {

    TNode *root = new_node();

    scanf("%d", &n);

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

        getchar();

        scanf("%s%d", str, &x);

        insert(root, str, x);

    }

    scanf("%d", &m);

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

        int flag = 1;

        scanf("%d", &x);

        ll ans = 0;

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

            getchar();

            scanf("%s", str);

            if (flag == 0) continue;

            int ret = find(root, str);

            if (ret == -1) flag = 0;

            ans += (ll)ret;

        }

        printf("%lld\n", flag == 0 ? -1 : ans);

    }

    clear(root);

    return 0;

}

巴特西

计蒜客劫富济贫 (Trie树)

最新文章

热门文章

巴特西

计蒜客 劫富济贫 (Trie树)

最新文章

热门文章

计蒜客劫富济贫 (Trie树)