uva 12526

字典树，可惜比赛的时候有两句话写倒了；
害得我调了一个小时；
今天不宜做题 = =
代码：
 1 #include<cstdio>
 2 #include<cstring>
 3 #define maxn 2600009
 4 using namespace std;
 5 
 6 struct node
 7 {
 8     bool flag;
 9     int cnt;
10     node *a[26];
11 } no[maxn];
12 
13 char s[100];
14 int ans,nonocount;
15 node *newnode()
16 {
17     node *p=no+nonocount++;
18     p->flag=0;
19     p->cnt=0;
20     for(int i=0; i<26; i++)
21         p->a[i]=NULL;
22     return p;
23 }
24 
25 void insert(node *rt,char *s)
26 {
27     int l=strlen(s);
28     int i=0;
29     while(1)
30     {
31         if(rt->a[s[i]-'a']==NULL) rt->a[s[i]-'a']=newnode();
32         rt=rt->a[s[i]-'a'];
33         rt->cnt++;
34         i++;
35         if(i==l)
36         {
37             rt->flag=1;
38             break;
39         }
40     }
41 }
42 
43 void query(node *rt)
44 {
45     int cot=0;
46     for(int i=0; i<26; i++)
47     {
48         if(rt->a[i]!=NULL)
49         {
50             cot++;
51             query(rt->a[i]);
52         }
53     }
54     if(cot>1)
55     {
56         ans+=rt->cnt;
57         if(rt->flag==1)ans--;
58     }
59     else if(rt->flag==1)
60     {
61         ans+=(rt->cnt-1);
62     }
63 }
64 
65 int main()
66 {
67     int n;
68     while(scanf("%d",&n)!=EOF)
69     {
70         nonocount=0;
71         node *p=newnode();
72         for(int i=0; i<n; i++)
73         {
74             scanf("%s",s);
75             insert(p,s);
76         }
77         ans=0;
78         query(p);
79         printf("%.2lf
",(double)(ans+n)/n);
80     }
81     return 0;
82 }
View Code