题解 P1291 【[SHOI2002]百事世界杯之旅】

· · 题解

我确信洛谷和网上的题解大部分都是错的，少部分是对的的也并没有说清楚。

比如说这个题极限的思想，我没有看到一个提出来的。

首先得明白一点，当已经买到所有的名字以后，是不需要再买的。针对于子问题也这样想。

从两个方面分别具体说说这个题目。

欢迎来博客阅读~

一、对每一步暴力极限求解。

令f[i]表示已经买到i个球星的期望购买次数。

我们由f[i]推f[i+1]

下一次购买可以买到不同球星的概率是\frac{n-i}{n}

下两次购买可以买到不同球星的概率是\frac{i}{n} \times \frac{n-i}{n} 注意到这时第一次买到的情况已经忽略了

...

下k次购买可以买到不同球星的概率是(\frac{i}{n})^{k-1} \times \frac{n-i}{n}

假设第k次就是正无穷次

则此步的期望即为

E=1 \times \frac{n-i}{n}+2 \times \frac{i}{n} \times \frac{n-i}{n}+3 \times (\frac{i}{n})^2 \times \frac{n-i}{n}+...+k \times (\frac{i}{n})^{k-1} \times \frac{n-i}{n}

则有

\frac{i}{n} \times E=1 \times \frac{i}{n} \times \frac{n-i}{n}+2 \times (\frac{i}{n})^2 \times \frac{n-i}{n}+3 \times (\frac{i}{n})^3 \times \frac{n-i}{n}+...+k \times (\frac{i}{n})^k \times \frac{n-i}{n}

错位相减

E\approx 1+\frac{i}{n}+(\frac{i}{n})^2+...(\frac{i}{n})^{k-1}

此步中采用极限的思想丢了一些0的项,用“\approx”表示采用极限思想，实际上极限是准确值，不需要“\approx”，此处只是为了标示，下同。

由等比数列公式

E=1+\frac{\frac{i}{n}-(\frac{i}{n})^k}{\frac{n-i}{n}}

\approx \frac{n}{n-i}

所以我们得出

f[i+1]=f[i]+\frac{n}{n-i}

则

f[n]=n \times (\frac{1}{1}+\frac{1}{2}+...+\frac{1}{n})

二、神奇的自己推自己的方法

同样令f[i]表示已经买到i个球星的期望购买次数。

如果从上一个推过来，为

f[i]+=(f[i-1]+1)\times \frac{n-(i-1)}{n}

如果从当前推过来，为

f[i]+=(f[i]+1)\times \frac{i}{n}

发现概率之和并不等于1，也就是说，这样写是有问题的。

从上一个推过来肯定没问题，我们考虑从当前推当前的意义。

“买了一个，买的是自己有的的概率”

然而我们考虑最开始说的一句话

“当已经买到所有的名字以后，是不需要再买的。”

也就是说，我们这样写可能把自己买了很多遍，而事实上是并不需要再买的。

于是我们修改一下意义

为“买了一个，买的是自己有的且不是自己的概率”

则推过来就是

f[i]+=(f[i]+1)\times \frac{i-1}{n}

那我们这个什么时候买呢？

极限的思想，在最后买时，对期望的影响是微乎其微的

把这两项加起来并化简

就得到了

f[i]=f[i-1]+\frac{n}{n-i+1}

和上一个方法的结果是一样的

关于合并两个值并不是一样的f[i]，用的也是极限的思想