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

scaulyd

这家伙很懒。。。

 
 
 

日志

 
 

2011 ICPC Regional Chengdu Site Precontest Problem E  

2011-09-11 20:31:49|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
好久没写过解题报告啦啦啦
做的时候以为虽然是N-1条边,但还可能有孤立点,可以有环,结果没想到,后来闻说是树,这样的数学期望咋能漏过不做。。。

题意,一棵树,从结点1出发,走,在每个结点 i 都有3种可能:
1.回到起点——>结点1 , 概率 Ki
2.结束退出,概率 Ei
3.随机走一条边
三个是同一个事件,而不是三个独立事件,即(Ki+Ei+随机走) == 1

对每个结点,设
ei = A*e1 + B*e[father[i]] + C(其实应该是Ai,Bi,Ci,写漏了)
一次dfs遍历
对叶子结点有:
ei = K[i]*e1 + E[i]*(e_exit=0) + (1-K[i]-E[i])*e[father[i]] + (1-K[i]-E[i]);
对非叶子结点,有:
ei = K[i]*e1 + E[i]*(e_exit=0) + (1-K[i]-E[i])*( 1/m*e[father[i]] + 1/m*sum(e[child]) + 1)
ei = K[i]*e1 + (1-K[i]-E[i])/m*e[father[i]] + (1-K[i]-E[i])/m*sum(e[child]) + (1-K[i]-E[i]);
m为结点i的边数
先dfs子节点,然后汇总,带入上式,同样可得一条:
ei = A*e1 + B*efa + C
直至代到e1=A*e1+B*(efa=0) +C,若A趋近于1,那无解,否则,谁都会求的吧。。。

这种题太对我胃口了。。。
  评论这张
 
阅读(1998)| 评论(7)
推荐 转载

历史上的今天

评论

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

页脚

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