讨论/技术交流/求助|最短路程和的期望/
求助|最短路程和的期望

题目如图:
题干.jpg
示例1.jpg
示例2.jpg

1
共 6 个回复

解答赞。但是要说这题水,就有点那个了吧

假设三家酒店为a,b,ca,b,c,那么所有处于路径(a,b)(a,b)(b,c)(b,c)以及(a,c)(a,c)上的边都会被正好走一次。

xix_i表示一次实验边ii产生的贡献,题目要求求E[i=1n1xi]=i=1n1E[xi]E[\sum_{i=1}^{n-1}x_i]=\sum_{i=1}^{n-1}E[x_i]。接下来可以单独考虑每条边的贡献。

Ai,Bi,CiA_i,B_i,C_i表示顶点ii子树下第1,2,31,2,3个人偏好的酒店数目。

对于E[xi]E[x_i],记边ii(ui,vi)(u_i,v_i),且viv_iuiu_i的孩子,则边ii被经过当且仅当有至少一个最多两个人选择viv_i子树中的酒店。而三个人选择酒店是独立的,第一人选择住下的概率为AviA1\frac{A_{v_i}}{A_1},其它类似。所以三个for循环暴力遍历,判断每个人是否在子树下选择酒店即可。算出概率pip_i后,E[xi]=piciE[x_i]=p_ic_i,其中cic_i是第ii条边的权重。

时间复杂度为O(n)O(n)的。

ali

你先告诉我这是哪家的笔试题,我再给你解答

hhh 求解答

现在招聘的笔试题都这么水吗