「中山纪中集训省选组D2T1」书堆 欧拉常数
2019-08-16 07:57:20来源:博客园 阅读 ()
「中山纪中集训省选组D2T1」书堆 欧拉常数
题目描述
蚂蚁是勤劳的动物,他们喜欢挑战极限。现在他们迎来了一个难题!蚂蚁居住在图书馆里,图书馆里有大量的书籍。书是形状大小质量都一样的矩形。蚂蚁要把这些书摆在水平桌子的边缘。蚂蚁喜欢整洁的布置,所以蚂蚁规定书本必须水平摆放,宽必须平行于桌缘(如图),而且不允许同一高度摆多本书。
蚂蚁想要让书本伸出桌子边缘尽量远,同时不让书因为重力垮下来。它们已经用不知道什么方法测出了书的长度\(M\)(如图)。如果总共有\(N\)本书,请你帮忙计算如何摆放使得最多水平伸出桌缘多远。你不用考虑蚂蚁用什么方法搭建这堆书。
如果某本书以上的所有书的重心的竖直射影不在这本书上,或者正好落在在这本书的边界上,那么这堆书是不稳定的,会因为重力而垮下来。
注意:
不考虑地球自转,重力系数也不因高度改变;
书是质量均匀,质地坚硬的理想二维物体;
在不会垮的前提下,每本书的位置坐标可以是任意实数。
输入格式
输入文件仅含一行,两个正整数\(N\)和\(M\),表示书本数和书本长度。
输出格式
输出仅包含一行,整数\(L\),表示水平延伸最远的整数距离 (不大于答案的最大整数,详见样例)
样例
样例输入1
1 100
样例输出1
49
样例输出1
2 100
样例输出2
74
数据范围
\(10\%\)的数据中\(N\leq5\);
\(20\%\)的数据中\(N\leq10^3\);
\(40\%\)的数据中\(N\leq10^7\);
\(100\%\)的数据中\(N\leq10^{18}\);答案\(\leq10^6\)。
题解
设\(f_i\)表示\(i\)本书达到最大位置时最下方的书与最上方的书的中点的距离。显然,\(f_1=0\)。
那么先考虑怎么通过\(f\)的前\(i\)个值计算出\(f_{i+1}\)。
记\(f\)的前缀和为\(g\),那么前\(i\)本书的总重心与最上方的书的中点的距离是\(\frac{g_i}{i}\)。而要保证伸出的距离最长,显然应该让上面\(i\)本书的总重心落在第\(i+1\)本书的边缘上。这样就会发现,\(f_{i+1}=\frac{g_i}{i}+\frac{M}{2}\)。这样,我们就可以递推计算答案了。
但是,\(N\)是\(10^{18}\)级别的,这样的递推公式没法满足我们,我们首先得将\(g\)消去。
考虑到\(g_i=g_{i-1}+f_i\),\(f_i=\frac{g_{i-1}}{i-1}+\frac{M}{2}\),将他们代入上式。
\[f_{i+1}=\frac{g_{i-1}+\frac{g_{i-1}}{i-1}+\frac{M}{2}}{i}+\frac{M}{2}=\frac{\frac{i\cdot g_{i-1}}{i-1}+\frac{M}{2}}{i}+\frac{M}{2}=\frac{g_{i-1}}{i-1}+\frac{M}{2}+\frac{M}{2i}=f_i+\frac{M}{2i}\]
这样,我们就有了用\(f_i\)求\(f_{i+1}\)的方法,也就知道了\(f_i=\sum_{k=1}^{i-1}\frac{M}{2k}\),而我们要求的\(N\)本书的最长延伸距离恰好就等于\(f_{N+1}\),也就是\(M\cdot\sum_{i=1}^{N}\frac{1}{2i}\)。我们只需要快速求出正整数的倒数和,就可以快速计算\(f\)了。
至于如何求正整数的倒数和呢?当\(N\leq10^7\)时,我们可以\(O(N)\)暴力求解,然而\(N\)更大的话就会超时。但同时我们可以注意到,答案不超过\(10^6\),相当于我们只要求出答案的前\(6\)位有效数字即可,于是我们可以借助欧拉常数计算,如下:
\[\gamma=\lim_{n\to\infty}\sum_{i=1}^{n}\frac{1}{i}-\ln(n)\]
于是当\(N\)很大时,我们可以用\(\ln(N)\)和\(\gamma\)相加求出正整数的倒数和的近似值。至于\(\gamma\)具体是多少,可以通过暴力计算\(\sum_{i=1}^{10^9}\frac{1}{i}\)与\(\ln(10^9)\)的差得出近似值,大约是\(0.57721566\)。
吐槽:这题不知道欧拉常数就做不了啊(虽然欧拉常数基本可以当成一个常识了)……不知道的人就算推出倒数和的形式也搞不出来啊……
\(Code:\)
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
ll n;
int m;
int main()
{
scanf("%lld%d", &n, &m);
if (n <= 10000000)
{
long double ans = 0;
for (int i = 1; i <= n; i++)
ans += 1 / (long double)i;
ans /= 2;
printf("%d\n", int(ans * m - 1e-6));
}
else
{
long double ans = (log(n) + 0.57721566) / 2;
printf("%d\n", int(ans * m - 1e-6));
}
}
原文链接:https://www.cnblogs.com/ModestStarlight/p/11289523.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:浅谈高精度算法(加减乘除)
下一篇:DP_Wooden Sticks
- 【NOIP2015普及组】 推销员(纪中数据-标准) 2019-08-16
- 2019.07.05 纪中_B 2019-08-16
- 中山纪念中学培训游记 2018-08-10
- BZOJ 2463: [中山市选2009]谁能赢呢?(智商) 2018-06-17
- BZOJ2440: [中山市选2011]完全平方数(莫比乌斯+容斥原理) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash