BZOJ 2318 Spoj4060 game with probability Problem

发布于 2017-06-13  101 次阅读


题目链接: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

 

 


一个非常弱的准退役OIER