洛谷P1291 [SHOI2002]百事世界杯之旅(期望DP)
2024-09-03 22:44:02
题目描述
“……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字,就可参加百事世界杯之旅的抽奖活动,获得球星背包,随声听,更克赴日韩观看世界杯。还不赶快行动!”
你关上电视,心想:假设有n个不同的球星名字,每个名字出现的概率相同,平均需要买几瓶饮料才能凑齐所有的名字呢?
输入输出格式
输入格式:
整数n(2≤n≤33),表示不同球星名字的个数。
输出格式:
输出凑齐所有的名字平均需要买的饮料瓶数。如果是一个整数,则直接输出,否则应该直接按照分数格式输出,例如五又二十分之三应该输出为(复制到记事本):
3 5-- 20 第一行是分数部分的分子,第二行首先是整数部分,然后是由减号组成的分数线,第三行是分母。减号的个数应等于分母的为数。分子和分母的首位都与第一个减号对齐。
分数必须是不可约的。
输入输出样例
输入样例#1: 复制
2
输出样例#1: 复制
3
说一种和楼上不一样的状态(本质是一样的)
我们用$f(i)$表示一共用$n$个不同的球星,已经收集到$i$个不同的球星
考虑转移,有两种状态
1. 买到不同时转移而来,概率为
$$\frac{n-i}{n}f(i-1)$$
2. 买到相同时转移而来,概率为
$$\frac{i}{n}f(i)$$
那么总共的情况就是
$$f(i)=\frac{n-i}{n}f(i-1)+\frac{i}{n}f(i)+1$$
化简得到
$$f(i)=f(i-1)+\frac{n}{n-i}$$
这个公式实际是在计算
$$n*\sum_1^n{\frac{1}{n-i}}$$
然后暴力算就可以了
#include<cstdio>
#define int long long int
int gcd(int a,int b){return b==?a:gcd(b,a%b);}
int calc(int x)
{
int base=;
while(x) base++,x/=;
return base;
}
main()
{
int N;
scanf("%lld",&N);
int up=,down=N;
for(int i=N-;i>=;i--)
{
up=up*i+down;down=down*i;
int r=gcd(up,down);
up/=r;down/=r;
}
up=up*N;
int r=gcd(up,down);
up/=r;down/=r;
if(up%down==) {printf("%lld",up/down);return ;}
int numa=calc(up/down),numb=calc(down);
for(int i=;i<=numa;i++) printf(" ");printf("%lld",up%down);puts("");//分子
if(up/down>) printf("%lld",up/down);for(int i=;i<=numb;i++) printf("-");puts("");//注意这里要特判
for(int i=;i<=numa;i++) printf(" ");printf("%lld",down);
return ;
}
最新文章
- Shopping(山东省第一届ACM省赛)
- mac boot2docker certs not valid with 1.7
- 2016 CCPC 合肥赛区 平行四边形//打铁记录..... 背锅还是我在行 此处@ctr 233
- emberjs创建类
- 简答的理解C语言中的各种类型函数
- VS调试Libevent流程
- UVALive 4043 Ants(二分图完美匹配)
- nosql数据库选型
- jvm理论
- EJB体系结构
- 1 IDEA 安装 及 IDEA开发 spring的环境搭建
- 从头到尾解析Hash表算法
- 可变与不可变类型数据,列表的copy方法
- C语言基础一(敲打键盘、寻找资料)
- vb中的除法
- python模块:hmac
- FineReport8.0如何连接FineIndex取数分析
- 【题解】 [NOI2009]变换序列 (二分图匹配)
- getParameter和getAttribute区别
- 【转】移除HTML5 input在type=";number";时的上下小箭头
热门文章
- datetime is null
- spring过滤器篇
- 【技术累积】【点】【java】【3】编译和反编译
- (转)shiro权限框架详解05-shiro授权
- BZOJ 1602: [Usaco2008 Oct]牧场行走 倍增裸题
- Integer Intervals POJ - 1716_查分约束_
- [USACO08NOV]奶牛混合起来Mixed Up Cows(状态压缩DP)
- --- Error: failed to execute &#39;.\ARMCC\bin\ArmAsm&#39;
- PatentTips - Optimizing power usage by factoring processor architectural events to PMU
- SVN中各种符号箭头含义