BZOJ 1174 [Balkan2007]Toponyms

发布于 2017-07-06  213 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1174

题意:给你一个字符集合, 你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀字符串的总个数最大化.


显然可以建立字典树,统计字数内单词个数,乘以深度更新答案即可.... 然而,爆空间

直接开一个 n*26 的数组记录儿子其实是很不优越的... 有一个对空间的优化就是用链式前向星存儿子

同时读入可以一个个 getchar,也能节约不少空间,于是就过了

 


一个非常弱的准退役OIER