[BZOJ 2048] [2009国家集训队]书堆 【调和级数】
2024-08-28 08:21:29
题目链接:BZOJ - 2048
题目分析
只有一本书时,这本书的重心落在桌子边缘上,伸出桌面的长度就是 1/2。
有两本书时,第一本书的重心就落在第二本书的边缘上,两本书的重心落在桌子边缘上,两本书的重心就是在最下面一本书的右端 1/4 处。那么伸出 1/2 + 1/4 。
三本书时,可以再多伸长 3 本书的重心 1/6 。
继续计算可以发现规律,i 本书的重心就落在最下面一本书的右端 1/2i 处。
那么我们要求的伸出的总长度就是 sigma(1 / 2i) = sigma(1 / i) / 2。
sigma(1 / 2i) 就是调和级数求和,如果 n 比较小,我们就直接 O(n) 求,因为 n 比较小的时候用极限公式求误差会比较大。
如果 n 很大,我们就用调和级数的极限公式 sigma(1 / i) (i = 1 to n) = ln(n + 1) + r。r 是欧拉常数,r = 0.5772156649015328...
然后就做完了。
代码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std; typedef double LF;
typedef long long LL; #define r 0.5772156649 const LF Eps = 1e-10; LL n, m; LF Ans; int main()
{
scanf("%lld%lld", &n, &m);
if (n <= 1000000ll)
{
for (int i = 1; i <= n; ++i)
Ans += 1.0 / (LF)i;
}
else Ans = log((LF)(n + 1)) + r;
Ans /= 2.0; Ans *= (LF)m;
printf("%d\n", (int)(Ans - Eps));
return 0;
}
最新文章
- 类型转换器(InitBinder 初始化绑定器)
- android-8~23 View.java - dispatchTouchEvent源码
- git 上传项目到github
- nyoj 38 布线问题
- ";use strict";
- 2016 Al-Baath University Training Camp Contest-1 A
- 解决DataSnap支持的Tcp长连接数受限的两种方法
- C#WinForm中在dataGridView中添加中文表头
- hdu 4405概率dp
- STL_vector
- HTML&;CSS基础学习笔记1.13—无序列表
- Web Api集成Swagger
- 【优先队列-求第Ki大的数】Black Box
- Markdown中使用mermaid画流程图
- 由会话信息保存认识ThreadLocal
- resin远程调试配置
- python接口自动化测试十六:unittest完成用例
- Vue+webpack项目中实现跨域的http请求
- Linux后门入侵检测工具
- Go之单元测试