题解 P1291 【[SHOI2002]百事世界杯之旅】
ButterflyDew
2018-07-27 12:24:35
我确信洛谷和网上的题解大部分都是错的,少部分是对的的也并没有说清楚。
比如说这个题极限的思想,我没有看到一个提出来的。
**首先得明白一点,当已经买到所有的名字以后,是不需要再买的。针对于子问题也这样想。**
从两个方面分别具体说说这个题目。
[欢迎来博客阅读~](https://www.cnblogs.com/ppprseter/p/9376392.html)
一、对每一步暴力极限求解。
令$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]$,用的也是极限的思想