P1481 魔族密码题目背景风之子刚走进他的考场就……花花当当当当~~偶是魅力女皇——花花^^华丽出场礼炮鲜花风之子我呕……杀死人的眼神快说题目否则……-_-###题目描述花花……咦好冷我们现在要解决的是魔族的密码问题自我陶醉搞不好魔族里面还会有人用密码给我和菜虫写情书咧哦活活当然是给我的比较多拉*_*。魔族现在使用一种新型的密码系统。每一个密码都是一个给定的仅包含小写字母的英文单词表每个单词至少包含111个字母至多757575个字母。如果在一个由一个词或多个词组成的表中除了最后一个以外每个单词都被其后的一个单词所包含即前一个单词是后一个单词的前缀则称词表为一个词链。例如下面单词组成了一个词链i\verb!i!iint\verb!int!intinteger\verb!integer!integer。但下面的单词不组成词链integer\verb!integer!integerintern\verb!intern!intern。现在你要做的就是在一个给定的单词表中取出一些词组成最长的词链就是包含单词数最多的词链。将它的单词数统计出来就得到密码了。风之子密码就是最长词链所包括的单词数阿……输入格式这些文件的格式是第一行为单词表中的单词数NNN1≤N≤20001 \le N \le 20001≤N≤2000下面每一行有一个单词按字典顺序排列中间也没有重复的单词。输出格式输出共一行一个整数表示密码。输入输出样例 #1输入 #15 i int integer intern internet输出 #14思路1看到全部是小写字母第一反应是trie树。思路是每插入一个单词就计算一下从第一个单词到当前这个单词的最长词链并更新答案。实现方法是插入单词的每个字符过程中记录遇到的每个节点的计数sum取最大值直到词尾将sum1记录进当前词尾节点的计数。代码如下#includebits/stdc.husingnamespacestd;constintN2000*80,M80;intn,tr[N][26],cnt[N],idx,ans;charstr[M];voidinser(chars[]){intp0;intsum0;for(inti0;s[i];i){intus[i]-a;if(!tr[p][u])tr[p][u]idx;if(cnt[p])summax(sum,cnt[p]);ptr[p][u];}cnt[p]sum1;ansmax(ans,cnt[p]);}intmain(){cinn;while(n--){cinstr;inser(str);}coutans;return0;}结果如下100分
P1481 魔族密码题目背景风之子刚走进他的考场就……花花当当当当~~偶是魅力女皇——花花^^华丽出场礼炮鲜花风之子我呕……杀死人的眼神快说题目否则……-_-###题目描述花花……咦好冷我们现在要解决的是魔族的密码问题自我陶醉搞不好魔族里面还会有人用密码给我和菜虫写情书咧哦活活当然是给我的比较多拉*_*。魔族现在使用一种新型的密码系统。每一个密码都是一个给定的仅包含小写字母的英文单词表每个单词至少包含111个字母至多757575个字母。如果在一个由一个词或多个词组成的表中除了最后一个以外每个单词都被其后的一个单词所包含即前一个单词是后一个单词的前缀则称词表为一个词链。例如下面单词组成了一个词链i\verb!i!iint\verb!int!intinteger\verb!integer!integer。但下面的单词不组成词链integer\verb!integer!integerintern\verb!intern!intern。现在你要做的就是在一个给定的单词表中取出一些词组成最长的词链就是包含单词数最多的词链。将它的单词数统计出来就得到密码了。风之子密码就是最长词链所包括的单词数阿……输入格式这些文件的格式是第一行为单词表中的单词数NNN1≤N≤20001 \le N \le 20001≤N≤2000下面每一行有一个单词按字典顺序排列中间也没有重复的单词。输出格式输出共一行一个整数表示密码。输入输出样例 #1输入 #15 i int integer intern internet输出 #14思路1看到全部是小写字母第一反应是trie树。思路是每插入一个单词就计算一下从第一个单词到当前这个单词的最长词链并更新答案。实现方法是插入单词的每个字符过程中记录遇到的每个节点的计数sum取最大值直到词尾将sum1记录进当前词尾节点的计数。代码如下#includebits/stdc.husingnamespacestd;constintN2000*80,M80;intn,tr[N][26],cnt[N],idx,ans;charstr[M];voidinser(chars[]){intp0;intsum0;for(inti0;s[i];i){intus[i]-a;if(!tr[p][u])tr[p][u]idx;if(cnt[p])summax(sum,cnt[p]);ptr[p][u];}cnt[p]sum1;ansmax(ans,cnt[p]);}intmain(){cinn;while(n--){cinstr;inser(str);}coutans;return0;}结果如下100分
