[SHOI2002]百事世界杯之旅
2024-08-23 13:11:49
题目:“……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字,就可参加百事世界杯之旅的抽奖活动,获得球星背包,随声听,更克赴日韩观看世界杯。还不赶快行动!”
你关上电视,心想:假设有n个不同的球星名字,每个名字出现的概率相同,平均需要买几瓶饮料才能凑齐所有的名字呢?
输入\(n(2\le n\le33)\),以带分数or整数的形式输出购买的期望数。
令\(f[i]\)代表集齐\(i\)个明星需要的瓶盖数量。我们很容易得到
\(\displaystyle f[i]=\frac{i-1}{n}f[i]+\frac{n-i+1}{n}f[i-1]+1\)
然后这个式子不清真,因为\(f[i]\)的递推式里有\(f[i]\)递推个蛋啊,所以对\(f[i]\)移项
\(\displaystyle \frac{n-i+1}{n}f[i]=\frac{n-i+1}{n}f[i-1]+1\)
然后再搞搞
\(\displaystyle f[i]=f[i-1]+\frac{n}{n-i+1}\)
行了,这是一个递推式的形式,完美。。。。。
所以\(\displaystyle f[n]=\sum_{i=1}^n\frac{n}{n-i+1}=\sum_{i=1}^n\frac{n}{i}\)
行了,这就完美了。。。
然后呢我们就给他加加加哎哎哎家家爱阿基爱家啊啊
自己写一个分数的结构体捣鼓就行了
最后输出的时候,为了安全我多写了点,如代码:
如果这个代码没有成功地高亮显示,说明你在浏览某LJ网站,请自觉的点我。拒绝lj网站从我做起
#include <bits/stdc++.h>
using namespace std;
#define int long long
int getlen(long long x, bool mode)
{
if(mode == 1 && x == 0)
return 1;
int ans = 0;
while (x > 0)
{
ans++;
x/= 10;
}
return ans;
}
struct fraction
{
long long son, mother;
fraction(int son = 0, int mother = 1) : son(son), mother(mother){}
void redution(){int g = __gcd(mother, son);mother /= g;son /= g;}
void print()
{
redution();
long long div = son / mother;
long long rest = son % mother;
if (rest == 0)
{
printf("%lld\n", div);
return;
}
int len = getlen(div, 0);
int len1 = getlen(rest, 1);
int len2 = getlen(mother, 1);
int len3 = max(len1, len2);
for (int i = 1; i <= len; i++)
putchar(' ');
printf("%lld\n", rest);
if (div > 0)
printf("%lld", div);
for (int i = 1; i <= len3; i++)
putchar('-');
printf("\n");
for (int i = 1; i <= len; i++)
putchar(' ');
printf("%lld\n", mother);
}
};
fraction operator+(const fraction &a, const fraction &b)
{
fraction ans(a.son * b.mother + a.mother * b.son, a.mother * b.mother);
ans.redution();
return ans;
}
signed main()
{
int n;
scanf("%lld", &n);
fraction ans;
for (int i = 1; i <= n; i++)
{
fraction tmp(n, i);
ans = ans + tmp;
}
ans.print();
return 0;
}
最新文章
- AOP动态代理解析1-标签的解析
- (已解决) 未能加载文件或程序集“Newtonsoft.Json, Version=4.0.0.0, Culture=neutral,
- Jsch
- mybatis like 查询
- Android中解析XML的方法
- Hibernate在关于一对多,多对一双向关联映射
- tomcat配置管理员-走后门
- Windows2008 R2上完全卸载Oracle操作步骤
- 阿里云IoT
- bank_card.js
- 和TransDecoder 学习perl 自定义模块的路径问题
- PHD实时数据对象
- 利用 T-sql 的从句 for xml path(&#39;&#39;) 实现多行合并到一行, 并带有分隔符
- mybatis源码追踪1——Mapper方法用法解析
- python中垃圾回收机制
- 很幽默的讲解六种Socket IO模型
- HDUOJ------1058 Humble Numbers
- C语言 &#183; 龟兔赛跑预测
- 【转载】php如何给APP端写接口
- 探讨Java I/O类和接口
热门文章
- wp8安装SSL证书
- 应用HTMLTestRunner整合测试报告
- PDM中列举所有含取值范围、正则表达式约束的字段
- 问题:oracle floor;结果:Oracle的取整和四舍五入函数——floor,round,ceil,trunc使用说明
- 《Android应用性能优化》 第6章 性能评测和剖析
- PopupWindow-----点击弹出 PopupWindow 初始化菜单
- Python 网络爬虫 001 (科普) 网络爬虫简介
- ROS Learning-003 beginner_Tutorials 创建ROS工作空间
- 关于photoshop处理图片的自动化
- CodeForces 141C Queue (构造)