【题解】P1291 百事世界杯之旅 - 期望dp
P1291 [SHOI2002]百事世界杯之旅
声明:本博客所有题解都参照了网络资料或其他博客,仅为博主想加深理解而写,如有疑问欢迎与博主讨论✧。٩(ˊᗜˋ)و✧*。
题目描述
“……在 \(2002\) 年 \(6\) 月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字,就可参加百事世界杯之旅的抽奖活动,获得球星背包,随声听,更克赴日韩观看世界杯。还不赶快行动!”
你关上电视,心想:假设有 \(n\) 个不同的球星名字,每个名字出现的概率相同,平均需要买几瓶饮料才能凑齐所有的名字呢?
输入格式
整数 \(n(2≤n≤33)\) ,表示不同球星名字的个数。
输出格式
输出凑齐所有的名字平均需要买的饮料瓶数。如果是一个整数,则直接输出,否则应该直接按照分数格式输出,例如五又二十分之三应该输出为(复制到记事本):\(5\dfrac{3}{20}\)
第一行是分数部分的分子,第二行首先是整数部分,然后是由减号组成的分数线,第三行是分母。减号的个数应等于分母的为数。分子和分母的首位都与第一个减号对齐。
分数必须是不可约的。
Solution
第一道期望 \(dp\) ,虽然说很水 但还是用了一些时间才弄懂的...
设目前已经拿了 \(i\) 个球星(由于球星是无序的,所以先拿后拿没区别),现在由 \(f_i\) 来推 \(f_{i+1}\)
则下一个瓶子能抽到不属于已拿的 \(i\) 个球星的概率为 \(\dfrac{n-i}{n}\)
下下个瓶子能抽到的概率,则是要求在下一个时抽到属于已拿 \(i\) 个中的瓶子,于是概率为 \(\dfrac{i}{n} * \dfrac{n - i}{n}\)
下下下个概率为 \(\left(\dfrac{i}{n}\right)^2*\dfrac{n - i}{n}\)
......
第 \(k\) 个瓶子的概率为 \(\left(\dfrac{i}{n}\right)^{k - 1} * \dfrac{n - i}{n}\)
此时的第 \(k\) 次为极限状态,无穷大次
则期望 \(E=1 * \dfrac{n-i}{n} + 2 * \dfrac{i}{n} * \dfrac{n - i}{n} + 3 * \left(\dfrac{i}{n}\right)^2*\dfrac{n - i}{n} + ... + k * \left(\dfrac{i}{n}\right)^{k - 1} * \dfrac{n - i}{n}\)
将式子两边乘以 \(\dfrac{i}{n}\) 得
\(\dfrac{i}{n}E= 1 * \dfrac{i}{n} * \dfrac{n - i}{n} + 2 * \left(\dfrac{i}{n}\right)^2*\dfrac{n - i}{n} + ... + k * \left(\dfrac{i}{n}\right)^{k} * \dfrac{n - i}{n}\)
两式错位相减再将等式两边乘以 \(\dfrac{n - i}{n}\) 得
\(E=1 + \dfrac{i}{n} + \left(\dfrac{i}{n}\right) ^ 2 + ... + \left(\dfrac{i}{n}\right) ^ k\)
有等比数列求和公式 \(\dfrac{a_1(1 - q^n)}{1 - q}\) 得
\(E=\left(\dfrac{n}{n - i}\right)\)
即 \(f_{i + 1} = f_i + \left(\dfrac{n}{n - i}\right)\)
通过递推合并提项得
\(f_n=n * \left(1 + \dfrac{1}{2} + \dfrac{1}{3} + ... + \dfrac{1}{n}\right)\)
这个式子是不是很漂亮很美观 \(2333\) ,接下来就很简单啦 如果忽略这恶心的输出格式
Code
#include<bits/stdc++.h>
#define ll long long
#define F(i, x, y) for(int i = x; i <= y; ++ i)
using namespace std;
int n;
struct node{
ll a, b;
}ans;
int weishu(ll x)
{
int k = 0;
while(x) x /= 10, ++ k;
return k;
}
ll gcd(ll x, ll y){return (x % y == 0) ? y : gcd(y, x % y);}
int main()
{
scanf("%d", &n);
ans.b = 1;
F(i, 1, n)
{
ans.a = ans.a * i + ans.b, ans.b = ans.b * i;
ll k = gcd(ans.b, ans.a);
ans.a /= k, ans.b /= k;
}
ans.a *= n;
ll k = gcd(ans.b, ans.a);
ans.a /= k, ans.b /= k;
if(ans.b == 1) {printf("%lld\n", ans.a); return 0;}
k = ans.a / ans.b, ans.a -= k * ans.b;
int l1 = weishu(k), l2 = weishu(ans.b);
F(i, 1, l1) printf(" "); printf("%lld\n", ans.a);
if(k) printf("%lld", k);
F(i, 1, l2) printf("-"); printf("\n");
F(i, 1, l1) printf(" "); printf("%lld\n", ans.b);
return 0;
}
最新文章
- ueditor插件简单使用
- mysql mybatis-generator plugin 分页
- JQuery_元素属性操作
- 微信App支付通知验签
- WPF学习笔记——认识XAML
- python数据持久存储:pickle模块的基本使用
- JavaScript的一些基本语句代码如下!!!!
- 如何在eclipse中添加android ADT
- CODEVS 1287 矩阵乘法
- 【转】Netty系列之Netty是什么
- HTML文档及标签介绍
- [译]Selenium Python文档:四、元素定位
- Gradle笔记——关于Gradle 1.12
- 关于用户与服务端密码的校验问题 !mysql php
- Scrapy框架-Item Pipeline
- [Swift]LeetCode76. 最小覆盖子串 | Minimum Window Substring
- Confluence 6 下载和安装 MySQL 驱动
- emoji表情softbank和unicode不兼容解决方案
- 【BZOJ4259】残缺的字符串
- bootstrap 图片切换