注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【TRIE树】【强连通向+搜索或者其他数学】【前缀单词】  

2013-07-29 15:18:33|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


一组单词是安全的,当且仅当不存在一个单词是另一个单词的前缀,这样才能保证数据不容易被误解,现在你手上有一个单词集合S,你需要计算有多少个子集是安全的。

注意:空集永远是安全的。

【输入】

第一行一个数n,表示集合大小,以下n行,每行一个由‘a..z’构成的字符串

【输出】

安全子集的个数

【样例输入】

3

hello 

hell

hi 

【样例输出】

6

数据规模

30%的数据满足: 1n10

100%数据满足:   1n50

字符串长度≤50,没有两个字符串是完全相同的。

==========================================================================

   一开始为了方便处理,想建立一棵TRIE树,但是算节点的时候算错了所以就没写了..TRIE树只需要50*50=2500个节点的,但是咱是以为没有用的地方都要建立,所以需要 26^50 个节点,这里肯定爆内存,所以说没有写TRIE树。标准做法是写TRIE树再做树型DP。不过咱还是直接叫递推了,首先,如果我们选择了某个点,那么它的子树下的单词就都不能选择了,那么我们假设只选择这个子树及该节点的方案总数,那么这个是与其他的树无关的,也就是说这是没有决策后效性的,于是我们设F[I]表示第i个节点以及其子树下的所有单词的方案数,那么设各个儿子为F[SI],那么根据乘法原理的话,我们再把I这个节点加进去考虑的话,则为 TT(F[SI])(不选择该节点,选择子树下的节点的)+1(只选择这个节点的) (注意假如这个节点上没有单词的话就不能加1了,这个可以用ORD(C[K])表示,当有单词的话标记为TRUE,其ASCII码值为1,否则为0),初始状态叶子节点均初始化为2即可。

   另外上面的方法在计算DP的时候标程使用的是递归,这样就不需要考虑FOR循环的顺序,而且本题也往往写不出什么顺序来。这里的方法就是DFS深搜的时候顺便计算好,为O(N)的,N为所有字符串的总长度,插入也是这个复杂度,所以总的复杂度就是O(N)。 

   然后就是自己的思考了,既然它要我们不要把有前缀的放一起,我们就一开始求出所有的符合的前缀来。这个的复杂度就是2500即可,然后我们可以知道,对于一个字符串S,如果存在P1,P2都是它的前缀,那么很显然P1,P2也不能放在一起。也就是说,S,P1,P2中只能选择一个,这看起来就有点像强连通分量的感觉,我们一开始使用暴力求出每个字符串的前缀的P1,P2,PI,对它们使用并查集来维护,这样我们就求出了一系列的强连通分量,但是这个强连通分量里面是有可能有重复的节点的。对于每一个强连通分量,我们再新加一个节点0表示未在这个强连通分量中选择元素,这样子的话就可以根据乘法原理做了。答案为 TT(M[I]) (m[i]表示强连通分量中元素的个数),但是由于强连通分量中可能有重复的元素,所以这个方法并不是完全正确的,如果直接交上去经试验只有40分。但是我们可以把它分为没有联系的和有联系的,没联系的就是指不存在强连通分量的,这一部分直接乘法原理求。而有联系的部分我们可以使用枚举情况搜索的方法.....(CB同学的想法...他想的比咱的现实多了,咱实在太理想了....),这样子做可以拿90分...当然为了精益求精咱们还必须继续努力,那么咱们可以试一试搜索并加一点剪枝,对于原字符串可以建图,对于P1是P2的前缀的时候我们就不在他们之间连边,对于其他的情况我们都可以连边,然后,同样可以使用递推之类的来求方案数,但是这可能很麻烦....

这里附一个咱写的TRIE树的AC程序


program prefix;

var t:array[1..2500,0..25]of longint;

    c:array[1..2500]of boolean;

    n,tot:longint;

    s:string;


function dfs(p:longint):int64;

var i:longint;

    ans:int64;

begin

  ans:=1;

  for i:=0 to 25 do

    if t[p,i]<>0 then ans:=ans*dfs(t[p,i]);

  exit(ans+ord(c[p]));

end;


procedure main;

var i,j:longint;

begin

  write(dfs(1));

  close(output);

end;



procedure insert(p:string);

var i,j,k,m:longint;

begin

  j:=length(p);

  i:=0;

  k:=1;

  while i<j do

   begin

     inc(i);

     m:=ord(p[i])-ord('a');

     if t[k,m]<>0 then k:=t[k,m]

                  else begin

                         inc(tot);

                         t[k,m]:=tot;

                         k:=tot;

                       end;

   end;

  c[k]:=true;

end;


procedure prepare;

var i,j:longint;

begin

  for i:=1 to 2500 do

    for j:=0 to 25 do

     t[i,j]:=0;

  fillchar(c,sizeof(c),false);

end;


procedure init;

var i:longint;

begin

  assign(input,'prefix.in');

  reset(input);

  assign(output,'prefix.out');

  rewrite(output);

  readln(n);

  tot:=1;

  prepare;

  for i:=1 to n do

    begin

      readln(s);

      insert(s);

    end;

end;


begin

  init;

  main;

end.



  

  评论这张
 
阅读(43)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018