HDOJ1251解题报告【字典树】-白红宇

HDOJ1251解题报告【字典树】

阅读量：4363 次

发布时间：2019-06-07

本文共 923 字，大约阅读时间需要 3 分钟。

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1251

题目概述：

　　给你一些单词和一些询问，对于每个询问求出所有单词中以询问为前缀的单词个数。

大致思路：

　　稍微修改一下Tire树就好了，对每个节点增加一个标记来记录到这个节点共有几个单词，这个题还需要注意用g++提交指针版的会MLE，所以需要用数组形式的Tire树。

　　年轻的我还是被输入给坑了……果然naive.

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
            8 #include 
            
              9 #include 
             
              10 #include 
              
               11 using namespace std;12 13 #define sacnf scanf14 #define maxn 100001015 #define inf 106110956716 #define Eps 0.00117 #define PI 3.141592718 #define mod 997319 #define MAXNUM 1000020 void Swap(int &a,int &b) { int t=a;a=b;b=t;}21 int Abs(int x) { return (x<0)?-x:x;}22 typedef long long ll;23 24 int tree[maxn][26];25 int cnt[maxn];26 int dir=1;27 28 void Insert(char *s)29 {30 int p=0,len=strlen(s);31 for(int i=0;i