前言
之前写过一篇大楼丢鸡蛋问题，今天看到以前写的东西纯属胡扯，所以重写一下，因为今天有幸见到了大楼丢鸡蛋的终极强化版本：$10^3 \times 10^{18}$。
题目
URAL - 1597
有一个 $N$ 层的大楼，你有 $K$ 个鸡蛋。每个鸡蛋的硬度都是相同的。碎鸡蛋不能用来测试。你要求出 至少扔多少次才能保证测出鸡蛋的硬度。
假设你在第 $x$ 层扔下鸡蛋，如果鸡蛋碎了，说明鸡蛋硬度不能承受在 $x$ 层扔下。如果没碎则说明鸡蛋硬度能承受在 $x$ 层扔下。
$N, K \leq 10^{18}$，$10^5$ 组数据，$0.5$ 秒
题解
$\mathcal O\left(KN^2\right)$ 做法
记 $f_{i, j}$ 表示用 $i$ 个鸡蛋测 $j$ 层高的楼的最少扔的次数。
首先，我们可以枚举一个 $k$，表示这次鸡蛋在第 $k$ 层扔。
那么就会有两种情况：
- 鸡蛋碎了，鸡蛋硬度在 $k$ 层以下，并且损失一个鸡蛋。所以 $f_{i, j} = 1 + f_{i - 1, k - 1}$。
- 鸡蛋没碎，鸡蛋硬度在 $k$ 层以上，并且没有损失鸡蛋。所以 $f_{i, j} = 1 + f_{i, j - k}$。
由于是求最坏情况，所以要取两者的最大值。而又由于我们可以决定在哪一层扔鸡蛋，所以我们在所有的 $k$ 中取最小值。
于是式子就是这样：
$$f_{i, j} = 1 + \min\limits_{k = 1}^j\max\left\{f_{i - 1, k - 1}, f_{i, j - k}\right\}$$
signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
tp k, n; bin >> k >> n;
if (k == 0 && n == 0) return 1;
vector f(k + 1, vector<tp>(n + 1));
for (tp i = 1; i <= n; ++i) f[1][i] = i;
for (tp i = 2; i <= k; ++i) {
for (tp j = 1; j <= n; ++j) {
f[i][j] = INF;
for (tp k = 1; k <= j; ++k) f[i][j] = min(f[i][j], max(f[i - 1][k - 1], f[i][j - k]) + 1);
}
}
bin << f[k][n] << '\n';
return 0;
}一个小优化：$\mathcal O\left(KN \log N\right)$
不是主线内容，可以跳过。
其实，随着 $k$ 的增加，$f_{i - 1, k - 1}$ 单调不减，$f_{i, j - k}$ 单调不增。所以 $\max\left\{f_{i - 1, k - 1}, f_{i, j - k}\right\}$ 的最小值在两函数交点处。所以我们可以二分求出这个交点。
signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
tp k, n; bin >> k >> n;
if (k == 0 && n == 0) return 1;
vector f(k + 1, vector<tp>(n + 1));
for (tp i = 1; i <= n; ++i) f[1][i] = i;
for (tp i = 2; i <= k; ++i) {
for (tp j = 2; j <= n; ++j) {
tp l = 1, r = j;
while (l <= r) {
tp mid = l + r >> 1, a = f[i - 1][mid - 1], b = f[i][j - mid];
if (a > b) r = mid - 1;
else l = mid + 1;
}
f[i][j] = min(f[i][j], max(f[i - 1][r - 1], f[i][j - r]) + 1);
}
}
}$\mathcal O\left(K \cdot Ans\right)$ 做法
现在做一个常用优化：设 $g_{i, j}$ 表示用 $i$ 个鸡蛋测 $j$ 次能确定的最高楼层。
于是我们有
$$g_{i, j} = g_{i - 1, j - 1} + 1 + g_{i, j - 1}$$
这个加 $1$ 是因为可以确定当前丢鸡蛋的这一层。
我们分析一下此时的复杂度：
状态数是 $K \cdot Ans$ 的，转移是常数的，因此总复杂度为 $\mathcal O\left(K \cdot Ans\right)$
我这里偷了点懒，写了个 $\mathcal O\left(KN\right)$。
signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
tp k = 1000, n = 1000;
vector g(k + 1, vector<tp>(n + 1));
for (tp i = 1; i <= n; ++i) g[1][i] = i;
for (tp i = 1; i <= n; ++i) {
for (tp j = 2; j <= k; ++j) {
g[j][i] = g[j - 1][i - 1] + 1 + g[j][i - 1];
if (g[j][i] >= n) {
while (j <= k) g[j++][i] = INF;
break;
}
}
}
[&]() -> void {
tp l = 1, r = n, tar = -1;
while (l <= r) {
tp mid = (l + r) / 2;
if (g[k][mid] >= n) { r = mid - 1; tar = mid; }
else l = mid + 1;
}
bin << tar << '\n';
}();
return 0;
}能过 $10^{18}$ 做法
此时要做我们的点睛一笔。我们发现 $g_{i, j}$ 的递推关系很像组合数的递推关系。
只需令 $h_{i, j} = g_{i, j} + 1$，此时 $h_{i, j} = h_{i - 1, j - 1} + h_{i, j - 1}$
这样就是组合数了。
但是我们并不需要这样做（
我们发现，当 $K \geq \log_2N$ 时，我们可以直接二分，这样是最优的（理性理解是去掉限制跑 DP）。
而 $K = 1, 2, 3$ 时，我们可以手动推公式算。
而 $K \geq 4$ 时，答案不超过 $7000$，因此，我们只需要计算 $64 \times 7000 = 448000$ 个 DP 值即可。
URAL - 1597：
// :/
tp log2(tp x) {
tp l = 1, r = x, ret = 0;
while(l<=r){
tp mid = (l+r) / 2;
++ret;
if (mid - l > r - mid) r = mid - 1;
else l = mid + 1;
}
return ret;
}
signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
tp k = 64, n = 1e5;
vector g(k + 1, vector<tp>(n + 1));
for (tp i = 1; i <= n; ++i) g[1][i] = i;
for (tp i = 1; i <= n; ++i) {
for (tp j = 2; j <= k; ++j) {
g[j][i] = g[j - 1][i - 1] + 1 + g[j][i - 1];
if (g[j][i] >= INF) {
while (j <= k) g[j++][i] = INF;
break;
}
}
}
while (static_cast<void>(bin >> k >> n), k != 0 || n != 0) {
if (k == 1) { bin << n << '\n'; continue; }
if (k == 2) {
tp l = 1, r = 2e9, tar = -1;
while (l <= r) {
tp mid = (l + r) / 2;
if (mid * mid + mid >= 2 * n) { r = mid - 1; tar = mid; }
else l = mid + 1;
}
bin << tar << '\n';
continue;
}
if (k == 3) {
tp l = 1, r = 2e6, tar = -1;
while (l <= r) {
tp mid = (l + r) / 2;
if (mid * mid * mid + 5 * mid >= 6 * n) { r = mid - 1; tar = mid; }
else l = mid + 1;
}
bin << tar << '\n';
continue;
}
if (k >= log2(n)) { bin << log2(n) << '\n'; continue; }
tp l = 1, r = 1e5, tar = -1;
while (l <= r) {
tp mid = (l + r) / 2;
if (g[k][mid] >= n) { r = mid - 1; tar = mid; }
else l = mid + 1;
}
bin << tar << '\n';
}
return 0;
}
void MIST() {
}
// :\ */