TopCoder SRM 626 Div1
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------------------
1000一眼看过去觉得太难了就没做...
------------------------------------------------------------
T1:
题意是说有两个人赌博,Alice扔a枚b面骰,Bob扔c枚d面骰,点数和较大的胜,已知Alice胜,求Alice的期望点数
啊哈!昨天学的条件概率!
设Alice的点数和为A,Bob的点数和为B
P(A = x|A > B) = P(A = x 且 A > B) / P(A > B)
设f[i][j]表示Alice投了i次,点数和为j的概率,随便DP一下就出来了
同样的g[i][j]表示Bob投了i次,点数和为j的概率
那么就有P(A > B) = Σ(i=1,max)Σ(j=1,i-1)f[a][i]*g[b][j]
P(A = x 且 A > B) = f[a][x] * Σ(j=1,x-1)g[b][j]
概率知道了,然后期望就不难求了
------------------------------------------------------------
600:
题意是在一张有向图带权上走最短路,并且有x次机会使得经过一条边的时候把这条边的边权变为负数,求最短路.图的大小<=50,x<=10^9
先跑一跑最短路,然后把x=1的情况(两点之间的最短路)求出来,建成矩阵A,那么(A^x)[1][n]就是答案
------------------------------------------------------------
评论 (0)
