Cyan's Blog

再也不换博客了，http://cyan.logdown.com/

换了一个新的名字囧...现在是http://coloairy.logdown.com/ (update on 8/28

OI姿势水平实在是太低了，我要认真搞OI了。

真的好多都不会好多都不熟，我竟然还天天颓。

不能再这样了QwQ

Description

有n个石子，A和B轮流做游戏，A先手，每次抛硬币，若正面朝上就拿走一枚石子，否则不作任何事。取到最后一颗石子的人胜利。AB都想取胜，A有p机率抛到想要的，B有q(p,q>=0.5)。求A获胜的概率。

Solution

设f[i]表示A为先手A赢的概率，g[i]为B为先手A赢的概率。

对于f[i]，显然从max(g[i],g[i-1])转移，g[i]类似，不过要从min转移。

那么有f[i]=p*g[i-1]+(1-p)*g[i],g[i-1]>g[i]

         g[i]=q*f[i-1]+(1-q)*f[i],f[i-1]<f[i]

讨论一下发现，若f[i-1]>g[i]那么f[i-1]<f[i]一定成立，反之亦然。

于是化简上面的式子得到

         f[i]=(p*g[i-1]+q*(1-p)*f[i-1])/(p+q-p*q);

Description

有n种不同的邮票，每一次买一张邮票，买到每种邮票的概率都是1/n，第k次买花费k元，求买齐n种不同的邮票需要的钱的期望。

Solution

设f[i]为目前有i种不同的邮票，到买完所有邮票还需要买的邮票数的期望(倒着考虑转移方便些>.<)。

考虑本次决策，显然有f[i]=(i/n)*f[i]+((n-i)/n)*f[i+1]+1。

移项化简得到，f[i]=f[i+1]+(n/(n-i))。

由于每次的花费不同，接着考虑，设g[i]为期望的钱数。

因为到达x局面时已经有期望次数f[x]，所以本次贡献为f[x]+1。

于是有g[i]=(i/n)*(g[i]+f[i]+1)+((n-i)/n)*(g[i+1]+f[i+1]+1)。

化简得到，g[i]=(i/(n-i))*f[i]+g[i+1]+f[i+1]+n/(n-i)。

通过dp愉快地解决了本题。

I'm Cyan，来自HN大弱校的蒟蒻。

从14年9月起，我成为了一名OIer，踏上了OI这条不归路。

我很喜欢算法和数学建模~>.<

在这个Blog上，我会放一些学习笔记和日常。

qq1278775128