UVA

题目链接：https://vjudge.net/contest/166647#problem/A

题意：

从一些字符串集合里面挑一子集，然后公共前缀长度*字符串个数最大；

分析：

将这些字符串放到一个字典树中，每个节点作为公共前缀(长度)*个数（边插入，边累加）

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 
 6 const int maxnode = (50000+5)*205;
 7 struct Trie {
 8     int ch[maxnode][2];
 9     int val[maxnode];
10     int sz;
11     int ans;
12     void init () {
13         ans = 0;
14         sz = 1;
15         memset(ch[0],0,sizeof(ch[0]));
16         memset(val,0,sizeof(val));
17     }
18     int idx(char c) {
19         return c - '0';
20     }
21 
22     void insert(char *s,int v) {
23         int u = 0,n = strlen(s);
24         for(int i=0;i<n;i++) {
25             int c = idx(s[i]);
26             if(ch[u][c]==0) {
27                 memset(ch[sz],0,sizeof(ch[sz]));
28                 ch[u][c] = sz++;
29             }
30             u = ch[u][c];
31             val[u] +=(i+1);
32             ans = max(ans,val[u]);
33         }
34     }
35 
36 }sol;
37 
38 char str[205];
39 
40 int main()
41 {
42     int t;
43     scanf("%d",&t);
44     while(t--) {
45         int n;
46         sol.init();
47         scanf("%d",&n);
48         for(int i=0;i<n;i++) {
49             scanf("%s",str);
50             sol.insert(str,1);
51         }
52 
53         printf("%d
",sol.ans);
54     }
55     return 0;
56 }

View Code