BNU OJ 29355 手速为王

题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=29355

与Trie树相关的计数问题。

因为正反各插了一次，所以字典中一共有2N个单词。

val[i]存储了在该位置有相同字母的单词的个数，对于在该位置的每个字母，2N-val[i]代表与其不同的单词个数，所以对于每个单词的每个位置的字母，不同的需要删，相同的不需要删。对于在该位置的所有单词，一共删的次数即为val[i]*( 2*N - val[i] )。

把每个位置都跑一边，最后的式子即为：ans += val[i]*( 2*N - val[i] )

这个方法也是从别人的代码里学来的，我能力有限，说不太清楚，请在式子中自己体会=3=

个人感觉这个计数方法很不错，我自己想想不出来。。。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 
 5 #define LL long long int
 6 
 7 const int MAXSIZE = 200100;
 8 const int sigma_size = 26;
 9 
10 struct Trie
11 {
12     int val[MAXSIZE];
13     int ch[MAXSIZE][sigma_size];
14     int sz;
15 
16     void init()
17     {
18         memset( val, 0, sizeof(val) );
19         memset( ch[0], 0, sizeof(ch[0]) );
20         sz = 1;
21         return;
22     }
23 
24     inline int idx( char cc )
25     {
26         return cc - 'a';
27     }
28 
29     void InsertStr( char *s )
30     {
31         int len = strlen(s);
32 
33         int u = 0;
34         for ( int i = 0; i < len; ++i )
35         {
36             int c = idx( s[i] );
37             if ( !ch[u][c] )
38             {
39                 memset( ch[sz], 0, sizeof(ch[sz]) );
40                 ch[u][c] = sz++;
41             }
42             u = ch[u][c];
43             ++val[u];
44         }
45 
46         u = 0;
47         for ( int i = len - 1; i >= 0; --i )
48         {
49             int c = idx( s[i] );
50             if ( !ch[u][c] )
51             {
52                 memset( ch[sz], 0, sizeof(ch[sz]) );
53                 ch[u][c] = sz++;
54             }
55             u = ch[u][c];
56             ++val[u];
57         }
58         return;
59     }
60 };
61 
62 Trie tr;
63 char str[MAXSIZE];
64 
65 int main()
66 {
67     int T;
68     scanf( "%d", &T );
69     while ( T-- )
70     {
71         tr.init();
72 
73         int N;
74         scanf( "%d", &N );
75         for ( int i = 0; i < N; ++i )
76         {
77             scanf( "%s", str );
78             tr.InsertStr( str );
79         }
80 
81         LL ans = 0;
82         for ( int i = 1; i <= tr.sz; ++i )
83             ans += tr.val[i] * ( N + N - tr.val[i] );
84 
85         printf( "%lld\n", ans );
86     }
87     return 0;
88 }

我能说这题的精华就是这一句ans += tr.val[i] * ( N + N - tr.val[i] )么……TAT……只要能想清楚这点，这题就很简单了。

最后想吐槽下自己：刚在赛场上看见这题的时候眼前一亮——哦哦哦Trieeeeee~~~终于找到一个我会的数据结构……OTL

然后一想计数问题就傻了，半天没搞明白。一直纠结于前缀有重叠，计数如何才能不重不漏云云……

单会数据结构，思路转化不来又有什么用……说到底还是跟不会一样……