【洛谷 P1666】 前缀单词 （Trie）

题目链接

考试时暴搜50分。。。其实看到“单词”，“前缀”这种字眼时就要想到\(Trie\)的，哎，我太蒻了。

以一个虚点为根，建一棵\(Trie\)，然后\(dfs\)，

以当前点为根的答案就是\(Ans_u=(\prod_{\text{v是u的子树}}Ans_v)+\text{有单词以这个点结尾 ? 1 : 0}\)，乘法原理嘛，如果有单词在这里结尾，那么就多一种情况：选这个单词且不选所有子树。

答案就是\(Ans_{\text{根}}\)

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);

#define Close fclose(stdin);fclose(stdout);

int n;

char a[60];

struct Trie{

    Trie *son[27];

    int p;

}*root = new Trie();

inline void Insert(){

    int len = strlen(a + 1);

    Trie *now = root;

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

       if(now->son[a[i] - 'a'] == NULL)

         now->son[a[i] - 'a'] = new Trie(), now->son[a[i] - 'a']->p = 0;

       now = now->son[a[i] - 'a'];

    }

    now->p = 1;

}

long long dp(Trie *now){

    long long sum = 1;

    for(int i = 0; i < 26; ++i)

       if(now->son[i] != NULL){

         sum *= dp(now->son[i]);

       }

    return sum + now->p;

}

int main(){

	Open("prefix");

	scanf("%d", &n);

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

		scanf("%s", a + 1), Insert();

	printf("%lld\n", dp(root));

	return 0;

}