题解 P4550 【收集邮票】

command_block

2018-12-29 23:35:39

Solution

深夜肝题纪念。 期望题道道都是神题,蒟蒻表示Orz。 ~~感觉我的思路没有那么麻烦。~~ 这道题题目描述有点模糊,并不是买第$i$种邮票需要$i$元,而是第$i$次买邮票需要$i$元。 假如皮皮花了x步收集了全部的邮票,那么花费就是$1+2+3+...+x=x(x+1)/2$(等差数列)。 化简得$(x^2+x)/2$。 我们就是要求$(x^2+x)/2$的期望。 **平方的期望不等于期望的平方。** 由于期望的线性性,可以转化为分别维护**平方的期望**与**线性期望**。 这种套路题都是要**倒推**。 设$p1[i]$为收集了$i$张邮票之后还要花费的次数的期望。$p2[i]$为收集了$i$张邮票之后还要花费的次数**平方**的期望。 易得$p1[n]=p2[n]=0$(都拿到了之后就不用收集了) 答案就是$(p2[0]+p1[0])/2$ 转移: $\Large{1.p1}$ $p1[i]=(i/n)(p1[i]+1)+(n-i)/n(p1[i+1]+1)$ 这个好理解,有(i/n)的概率买到已有的,这时候花费**变**为(p1[i]+1); 有(n-i)/n的概率买到没有的,这时候花费**变**为(p1[i+1]+1); 像解一元一次含参方程一样: $p1[i]=(i/n)(p1[i]+1)+(n-i)/n(p1[i+1]+1)$ $p1[i]=(i/n)p1[i]+(n-i)/n*p1[i+1]+1$ $(n-i)/n*p1[i]=(n-i)/n*p1[i+1]+1$ $p1[i]=p1[i+1]+n/(n-i)$ $\Large{1.p2}$ 开始麻烦了。 想了解更多非线性期望套路,见[P1654 OSU!](https://www.luogu.org/problemnew/show/P1654)一题。 $p2[i]=i/n*(p2[i]+2*p1[i]+1)+(n-i)/n*(p2[i+1]+2*p1[i+1]+1)$ 老样子,有(i/n)的概率买到已有的,有(n-i)/n的概率买到没有的。 前者花费**变**为(花费的次数+1)的平方的期望,因为$E((x+1)^2)=E(x^2)+2E(x)+1$,所以得$(p2[i]+2*p1[i]+1)$ 同理后者花费**变**为$(p2[i+1]+2*p1[i+1]+1)$ 理解了上面的式子,下面就是套路化简。 $p2[i]=i/n*(p2[i]+2*p1[i]+1)+(n-i)/n*(p2[i+1]+2*p1[i+1]+1)$ $p2[i]=i/n*p2[i]+i/n*(2*p1[i]+1)+(n-i)/n*(p2[i+1]+2*p1[i+1]+1)$ $(n-i)/n*p2[i]=i/n*(2*p1[i]+1)+(n-i)/n*(p2[i+1]+2*p1[i+1]+1)$ $p2[i]=i/(n-i)*(2*p1[i]+1)+p2[i+1]+2*p1[i+1]+1$ 推完了式子之后,代码就很简单了。 Code: ```cpp #include<cstdio> using namespace std; int n; double p2[10500],p1[10500]; int main() { scanf("%d",&n); p2[n]=0;p1[n]=0; for (int i=n-1;i>-1;i--){ p1[i]=p1[i+1]+1.00*n/(n-i); p2[i]=1.00*i/(n-i)*(2*p1[i]+1)+p2[i+1]+2*p1[i+1]+1; }printf("%.2lf",(p1[0]+p2[0])/2); return 0; } ```