当前位置：首页 > news >正文

P4820 [国家集训队] 书堆题解

news 2026/3/26 23:30:23

题意简析

求在保证稳定的前提下，将 \(n\) 本长度为 \(m\) 的书叠放在桌子边缘，最右端伸出桌面的最长长度。

思路解析

物理

理论推演

相信大家在初中物理学习时，一定遇到过经典的“堆叠书本”问题，回顾我们当时的思路我们是如何解决这个问题的？

还记得我们当时的时候在学力学，学力学中的重力。根据牛顿第一定律：

每个物体将保持静止或匀速直线运动，除非有外力改变其运动状态。

发现这里的每一本书都是相对于桌面静止的，那么我们容易对单独一个书本进行受力分析：

这里光有重力显然不平衡，所以显然有向上的支持力。

根据牛顿第三定律：

对于每一个作用力，都会有一个大小相等、方向相反的反作用力。

也就是说其对下面的物体有压力。

但是我们都知道，压力的作用并不好分析，因为它是的本重是弹性形变产生的弹力。那么我们怎么简化呢？

我们想到，我们在做各类科学实验的时候，常常用到一种方法叫做等效替代法，也就是说只要最终效果是一样的，那么我们并不需要去关注中间的过程如何实现的。

就比如说平面镜成像实验中的放在玻璃片后蜡烛，本重上玻璃片后的真实摆放的蜡烛并不是像，但是效果一样，且我们容易观测和测量出距离，所以我们就采用等效替代法来分析。

这里，我们可以把每本书看成一个质点，因为重力和压力的作用效果都一样（压强不一样，但在这道题中与要求的无关，所以可以采用该方法）。

问题转化

我们现在来正式解决问题。

由易入难，先看只放 \(1\) 个的情况：

显然我们把重心刚刚好放在桌面边缘，那么最长的距离就是 \(\frac{m}{2}\)。

现在考虑放 \(2\) 个：

还是沿袭之前的思路，我们考虑把这两个书本看成一个整体，那么这个整体的重心应该在桌面的最边缘；考虑把桌面和下面的书本看成一个整体系统，然后最上面的书本依旧是伸出 \(\frac{m}{2}\) 的距离。再考虑下面的书，因为其质量和上方的书是相等的，那么其“权重”就和上面的书一样。根据三角形相似和全等的知识，于是这两本书到整个组合体的重心的距离也应该是相等的。

如图所示，下面的书本就最多伸出 \(\frac{m}{4}\) 的距离。

可能已经有较为明显的规律了，但我们不清楚下面一个是 \(\frac{m}{6}\) 还是 \(\frac{m}{8}\)，所以现在考虑放 \(3\) 个：

我们把三本书看成一个整体，系统平衡，重心在桌子的最边缘。继承以前的最优解，把上面的两本书看成一个整体，其质量为是一本书的两本，那么其在组合体中的权重就是 \(2\)，而下面那本书的权重是 \(1\)。所以它们到重心的距离是 \(2 : 1\) 的关系，就占到了 \(\frac{m}{2}\) 的 \(\frac{1}{3}\) 即 \(\frac{m}{6}\)。

推广到 \(n\) 本书，我们可以得到一定有 \(n-1\) 本书压在 \(1\) 本书上，那么其最长的距离就是 \(\frac{m}{2} \times \frac{1}{(n-1)+1} = \frac{m}{2n}\)。

但需要注意的是本题中，正好的情况被看作不稳定，所以要向左移动一个极小值 \(\epsilon\)。

数学

考虑如何求和？我们把 \(\frac{m}{2}\) 提出来，发现剩下的式子是：

\[H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \]

这个东西就是大名鼎鼎的调和级数。这个级数有一个众所周知的性质就是这个级数是发散的，只是增长的比较慢。（~~也许可以打表？~~）

如果 \(n \le 10^7\)，那么直接 \(O(n)\) 计算即可；但是题目中说 \(n \le 10^{18}\) 显然我们需要有 \(O(\log (n))\) 或 \(O(1)\) 做法。

因为调和级数有以下渐进形式：

\[H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \cdots \]

那么我们考虑到 \(n\) 很大，我们只取到 \(n^4\)。这里的 \(\gamma = 0.57721566490153286 \cdots\) 为欧拉-马歇罗尼常数。

最后再取整数输出即可。时间复杂度为 \(O(n)\) 或 \(O(1)\)，空间复杂度 \(O(1)\)。

代码实现

#include <bits/stdc++.h>
#define int long long
#define Gamma 0.57721566490153286060651209008240243104215933593992L
using namespace std;
typedef long double ld;
const int MAXN = 1e7;
ld H;
int n, m;
signed main() {cin >> n >> m;if (n <= MAXN) {for (int i = 1; i <= n; ++i) {H += 1.0L / i;}} else {ld N = n;H = logl(N) + Gamma + 1.0L / (2.0L * N) - 1.0L / (12.0L * N * N) +1.0L / (120.0L * N * N * N * N);}cout << (int)((m * H / 2.0L) - 1e-12L);return 0;
}