题解：P13268 [GCJ 2014 Finals] Allergy Testing

brbrbread · 2025-07-15 10:27:50 · 题解

这是一篇通过AI翻译的官方题解 本人不会这道题，也不知道能不能这样提交题解，如果不能，那我要对审核这篇题解的管理员提前道一下歉,很抱歉浪费了您的时间。

官方题解

我们介绍两种解题策略。

1. 首先是动态规划解法
2. 然后是更直接的组合解法。

但本篇题解只介绍第一种方法。

基于食物数量的动态规划

乍一看，这像是一个标准的动态规划问题，我们要计算出在 N 种食物中找出致敏食物所需的最少天数。我们可以把 N 种食物分成两组，对其中一组进行实验（即吃下第一组中的所有食物），然后等待结果。如果凯利出现过敏反应，那么致敏食物就在第一组中，否则就在第二组中。所需的天数取决于解决每个较小集合所需的天数。 我们可以尝试第一组所有可能的分割大小，这样会得到一个 O (N^2) 的解法。我们注意到，对于 N 来说，最优的分割大小总是至少和 N-1 的最优分割大小一样大，由此可以将其改进为 O (N) 的解法。所以我们只需要考虑从之前的分割大小开始的分割大小，总共只需要考虑 O (N) 个分割位置。看看小输入的约束条件，其中 N 最大可以达到 10^{15}，很明显这不是一个可行的方法。然而，这种方法可能会为我们提供一些改进解法的思路（我们将在下一节中看到）。 你可能会想，为什么将 N 种食物平均分成两组，然后对其中一组进行实验并不能得到最优答案。考虑这样一个例子：A=1，B=100，N=4。在这种情况下，出现过敏反应的代价非常高。最好是一次只对一种食物进行实验，因为一旦凯利吃下了致敏食物，她第二天就会知道，这样整个过程最多只需要 3 天。但如果她把食物分成两组，每组 2 种，并对其中一组进行实验，她可能会出现过敏反应，却仍然无法确定致敏食物，还得等 100 天才能进行下一次实验。因此，将 N 种食物平均分割可能不会得到最优解。

基于天数的动态规划

在研究一些 A 和 B 最多为 100 的小案例后，你会发现即使 N 很大，所需的最少天数也只在几千的范围内。这提示我们，使用天数作为动态规划的状态可能会高效得多。我们可以用动态规划来计算 max_foods_d，即凯利在最多 D 天内能够确定致敏食物的最大食物数量。如果我们能快速计算出 max_foods_D，那么我们可以通过找到最小的 X，使得 max_foods_X\ge N，从而得到最终答案。 为了计算 max_foods_D，我们要构建一棵满二叉树，它代表一种在最多 D 时间内处理最大可能数量食物的策略。树中的每个节点对应一组食物。凯利从根节点开始，进行一系列测试。每次测试都会缩小食物的范围，然后她会移动到对应的节点。为了做到这一点，她会吃下当前节点右子节点中的所有食物。如果她没有出现反应，就移动到左子节点；如果出现了反应，就移动到右子节点。树的叶节点对应单一的食物。当凯利到达叶节点时，她就已经找出了她过敏的食物，可以停止了。 定义节点的 “高度” 为该节点剩余的天数。根节点的高度为 D，其他每个节点的高度至少为 0。如果一个节点的高度为 X，那么它的左子节点的高度为 X-A，因为凯利需要 A 天才能知道自己没有出现反应。如果右子节点是叶节点，那么它的高度为 X-A；否则，它的高度为 X-B。这是因为如果凯利在反应消退后需要进行另一次测试，她只需要等待 B 天。 定义节点的 “值” 为该节点所对应的食物集合的大小。让我们来看一个例子，一个高度为 D、值为 max_foods_D = max$foods{D-A} + max_foods _{D-B}$ 的节点：
天数

……

左子节点的高度为 D-A 天，其值为 max$foods{D-A}。右子节点的高度为 D-B 天，其值为 max_foods{D-B}。这意味着如果凯利有 D 天的时间和 max$foods_{D-A} + max$foods{D-B} 种食物需要处理，她可以把这些食物分成两组：第一组有 max_foods{D-A} 种食物，第二组有 max$foods_ {D-B} 种食物。 如果这棵树对应一种处理 max_foods_D 种食物的策略，那么每个子树在给定的时间约束下必须包含尽可能多的节点，否则我们可以通过改变那个子树来得到更好的策略。 因此，如果一个节点 A 可以处理不止一种食物，那么它的值必须是 max$foods {(height (A))}。 对于只能处理一种食物的叶节点，情况更为复杂。如果该节点是其父节点的左子节点，那么它的高度必须小于 A，否则我们就可以在那里处理至少两种食物了。如果该节点是其父节点的右子节点，那么它的高度只需要小于 B。这是因为如果再增加一种食物，凯利必须在前一次测试后等待 B 天，而不是 A 天。 让我们来看一个例子，当 A=2，B=3 时，我们要计算 max_foods (8)$。我们可以构建如下的满二叉树：
天数:

根节点的高度为 8 天。按照上面描述的规则，我们可以继续遍历子节点，直到到达叶节点。从叶节点一直向上到根节点，我们可以通过将两个子节点的值相加来计算中间节点的值。从上面的图中，我们可以得出 maxfoods (8)=9，同样地，maxfoods (6)=5，max_foods (5)=4 等等。 具有相同高度的节点总是具有相同的值（除了作为右子节点的叶节点这种情况）。 因此，我们可以使用记忆化来在 O (所需天数) 的时间内完成计算。下面是 Python 3 中的一个示例实现：

from functools import lru_cache
@lru_cache (maxsize=None) # 记忆化。
def max_foods (D, A, B):
if D < A:
return 1 # 叶节点。
return max_foods (D - A, A, B) + max_foods (D - B, A, B)

我们也可以在这里使用二分查找。

def min_days(N, A, B):
days = 0
while max_foods(days, A, B) < N:
days += 1
return days
for tc in range(int(input())):
print("Case #%d: %d" % (tc + 1, min_days(*map(int, input().split()))))

上述解决方案假设答案（即天数）限制在几千天以内，对于 A 和 B 最多为 100 的小输入案例来说确实如此。对于大输入案例，A 和 B 可以达到 10^{12}，这使得上述解决方案不可行。 基于每种类型边的数量的动态规划 注意到对于较大的 A 和 B，max_foods (D) 大于 max_foods (D-1) 的天数集合 D 是稀疏的。每条边会将剩余时间减少 A 或 B。我们称这些边为 A 边和 B 边。由于节点的高度只取决于从该节点到根节点路径上的 A 边和 B 边的数量，我们可以使用一种更 “紧凑” 的动态规划状态来计算 max_foods (D)，即使用 A 边和 B 边的数量，而不是像 Python 3 中的示例实现那样使用高度：

INF = 1e16
def max_foods (D, A, B):
ans = 0
mem = [0] * 60 # 60 个元素的零数组。
mem [0] = 1
for i in range (int (D / A + 1)): # A 边。
for j in range (int (D / B + 1)): # B 边。
H = i * A + j * B # 该节点的高度。

如果该节点使用的天数超过 D，则跳过。

if H > D:
break

累加子节点的值。

if j > 0 and H + A <= D:
mem[j] += mem[j - 1]

如果离 D 太近而无法添加 B 边， 则右子节点是叶节点， 因此将该节点添加到答案中。

if H + B + A > D:
ans += mem[j]
避免溢出。
ans = min(ans, INF)
mem[j] = min(mem[j], INF)
return ans

注意到上述代码在迭代 A 边时重用了动态规划数组，并且 B 边的数量限制在 60 以内，因此内存占用非常小。然而，当 A 边的数量非常大时，这种方法就不起作用了。A 边的数量可以高达 50 \times B \div A，因此这种解决方案是否有效与 B \div A 的比率密切相关。在接下来的两节中，我们提供了两种解决方案来解决这个问题。
解决方案 1：对 B 边数量 \le2 使用闭式解 注意到随着 B \div A 的比率增大，解决方案中 B 边的数量最终会非常少，而 A 边的数量最终会非常多（这使得上面的动态规划解决方案运行非常缓慢）。事实上，如果 B \div A > N，那么解决方案将不涉及任何 B 边。这对应于一种一次尝试一种食物，直到找到正确食物的策略。如果解决方案中最多有 0、1 和 2 条 B 边，分别对应树高 <B+A、<2B+A 和 < 3B+A，我们可以推导出计算 max_foods_D 的闭式解。对于