标签：邮票 集齐 期望 选到 240503 选讲 好题 double frac

240503好题选讲：概率和期望

期望的计算公式：

\[E(X)=\sum_i i\times P(x=i) \]

期望的线性性：

\[E(X+Y)=E(X)+E(Y),E(kX)=kE(x) \]

---

A 百事世界杯之旅

B 收集邮票

• 一句话题意：\(n\) 种邮票，每次等概率选取一张，第 \(i\) 张的价格是 \(i\), 问：

• 标准版：集齐 \(n\) 种邮票所需要购买的期望张数。

  • 记 \(f_i\) 表示已经收集到 \(i\) 种邮票, 集齐剩余邮票的期望张数.

  • 则有 \(f_n=0\) , 答案为 \(f_0\).

  • 则有转移方程:

\[f_i=\frac{i}{n} (f_i+1)+\frac{n-i}{n}(f_{i+1}+1) \\ =1+\frac{i}{n}f_i+\frac{n-i}{n}f_{i+1} \]

​ 即:下一步要么选到一样的,要么选到新的,再乘上各自的权重即可.

​ 则

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

• 进阶版：集齐 \(n\) 种邮票所需要购买的期望价格.

  • 另记 \(g_i\) 表示已经收集到 \(i\) 种邮票, 集齐剩余邮票的期望价格.

  • 则有转移方程:

    \[g_i=\frac{i}{n}[\ (f_i+1)+g_i\ ] + \frac{n-i}{n}[\ (f_{i+1}+1)+g_{i+1}\ ] \]

    即:下一步要么选到一样的( 则下一步的花费是 \(f_i+1\) ),要么选到新的( 则下一步的花费是 \(f_{i+1}+1\) ) ,再乘上各自的权重即可.

    则

    \[g_i=\frac{n}{n-i}+\frac{i}{n-i}f_i+f_{i+1}+g_{i+1} \]

#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=r;++i)
#define G(i,r,l) for(int i(r);i>=l;--i)
using namespace std;
using ll = long long;
const int N=1e4+5;
double f[N],g[N];
int n;
signed main(){
	scanf("%d",&n);
	f[n]=0,g[0]=0;
	G(i,n-1,0) f[i]=f[i+1]+(double)n/(n-i);
	G(i,n-1,0) g[i]=(double)n/(n-i)+(double)i/(n-i)*f[i]+f[i+1]+g[i+1];
	printf("%.2lf",g[0]);
	return 0;
} 

标签：邮票,集齐,期望,选到,240503,选讲,好题,double,frac
From： https://www.cnblogs.com/superl61/p/18198680