BZOJ 2318 Spoj4060 game with probability Problem


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2318

题意:两个人玩游戏,投掷硬币后若正面朝上,取走一个硬币,换下一个人,取走最后一个硬币的获胜。每个人在投掷时分别有 p,q 的概率投到自己想要的一面,问先手胜利概率...


\(f_i\) 表示 A 先手时剩 i 个石子胜率 \(g_i\) 表示 A 后手时剩 i 个石子的胜率 x 表示 A 投正面的概率 y 表示 B 投正面的概率

$$f_i=xg_{i-1}+(1-x)g_i$$

$$g_i=yf_{i-1}+(1-y)f_i$$

整理使得等式左边只与 i 有关,右边只于 i-1 有关,便于递推 (式子比较长就不放上去了...

显然若\(f_{i-1}>g_{i-1}\) 则先手不想投中,否则则想

不想投中时取 x=1-p, y=1-q 即可

另外此题不能直接\(O(n)\) 递推,实际上,当 n 很大时 概率的变化很小,所以只需要推到几百即可。

此处蒟蒻只能打表得出,并不知道为什么?该数列收敛于某值吗? 还是单纯变化很慢精度可以接受? 望路过神犇解答,thx

 

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2318 Spoj4060 game with probability Problem


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,