【SHOI 2002】百事世界杯之旅概率期望

2019-11-08 01:20:29

字体：大中小

来源：转载

供稿：网友

题目描述

　　……在2003年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可以参加百事世界杯之旅的抽奖活动，获取球星背包、随身听，更可以赴日韩观看世界杯。还不赶快行动！……” 　　你关上电视，心想：假设有n个不同球星的名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？

题目大意

略

数据范围

2<=n<=33

样例输入

样例输出

11(5/12)

解题思路

　　假设当前已经收集了i的球员的瓶盖，如果要收集第i+1个球员的瓶盖概率为1-i/n。设f[i]为收集i个球员的瓶盖的期望瓶数。　　f[i]=1*(1-i/n)+(f[i]+1)*(i/n) 　　f[i]=(1-i/n)+f[i]*(i/n)+i/n; 　　f[i]*(1-i/n)=1-i/n+1/n 　　f[i]=1/(1-i/n) 　　f[i]=n/(n-i) 　　所以答案就是这里写图片描述

代码

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>using namespace std;inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}long long A=0,B=1,GCD,LCM,t;void Add(long long &x,long long &y,long long a,long long b){//通分相加 GCD=__gcd(y,b),LCM=y*b/GCD;//库里自带gcd，似乎比赛不能用 x*=(LCM/y); a*=(LCM/b); y=LCM; x+=a; GCD=__gcd(x,y); x/=GCD; y/=GCD;}int main(){ int n; cin>>n; for(int i=1;i<=n;i++) Add(A,B,n,i);//A/B+n/i cout<<A/B; if(A%B){ t=A/B; A-=B*t; cout<<"("<<A<<"/"<<B<<")"; } return 0;}

上一篇：夕拾算法进阶篇：27)并查集

下一篇：树莓派设置默认声卡