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

官方题解

我们介绍两种解题策略。

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

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

基于食物数量的动态规划

乍一看，这像是一个标准的动态规划问题，我们要计算出在 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 max$

foods_{D-A} + max

$foods_{D-B}$ $D-A max$

foods_{D-A}

……

D-B 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 9\\ 7\\ 6 5\\ 5\\ 4 3\\ B=3 2 2\\ A=2 2 \\ 1\\ 0\\

根节点的高度为

8

天。按照上面描述的规则，我们可以继续遍历子节点，直到到达叶节点。从叶节点一直向上到根节点，我们可以通过将两个子节点的值相加来计算中间节点的值。从上面的图中，我们可以得出

max

$foods (8)=9$ ，同样地， $max$

foods (6)=5

，

max

foods (5)=4

等等。具有相同高度的节点总是具有相同的值（除了作为右子节点的叶节点这种情况）。因此，我们可以使用记忆化来在

O

(所需天数) 的时间内完成计算。下面是 Python 3 中的一个示例实现：

PYTHON


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)

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

PYTHON

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 中的示例实现那样使用高度：

PYTHON

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，则跳过。

PYTHON

if H > D:
break

累加子节点的值。

PYTHON

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

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

PYTHON

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$ 的闭式解。对于 $B \div A$ 比率大于 $200,000$ 的情况，最大树高小于 3B+A，因此我们可以从这些闭式解中得到解决方案。如果比率小于 $200,000$ ，我们可以回到我们的动态规划解决方案。下面是 Python 3 中计算 $max$

foods_D

的闭式解的示例实现，其中解决方案中最多有

0

（线性）、

1

（二次）或

2

（三次）条

B

边：

CPP

def linear(D, A, B):
return int(D / A + 1)
def quadratic(D, A, B):
R = int((D - B) / A)
if INF / R < R:
return INF
return int(linear(D, A, B) + (R * (R + 1)) / 2)
def cubic(D, A, B):
ans = quadratic(D, A, B)
a = int((D - 2 * B) / A)
for i in range(a):
R = a - i
if INF / R < R:
return INF
ans += int((R * (R + 1)) / 2)
if ans > INF:
return INF
return ans

综上所述，我们可以确定使用哪种闭式解，或者使用紧凑的动态规划作为备选方案，然后使用二分查找来找到所需的最少天数。下面是代码的其余部分：

PYTHON

def binary_search(N, A, B, low, high, func):
while high - low > 1:
D = int((high + low) / 2)
if func(D, A, B) >= N:
high = D
else:
low = D
return high
def min_days(N, A, B):
if cubic(3 * B + A, A, B) + 1 >= N:
return binary_search(N, A, B, 3 * B + A, 51 * B, max_foods)
if cubic(2 * B + A, A, B) >= N:
return binary_search(N, A, B, 2 * B + A, 3 * B + A, cubic)
if quadratic(B + A, A, B) >= N:
return binary_search(N, A, B, B + A, 2 * B + A, quadratic)
return binary_search(N, A, B, -1, B + A, linear)
for tc in range(int(input())):
print("Case #%d: %d" % (tc + 1, min_days(*map(int, input().split()))))

cpp 解法由AI提供

CPP

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

// 记忆化缓存：存储(max_foods(D, A, B))的结果
unordered_map<ll, unordered_map<ll, unordered_map<ll, ll>>> memo;

// 基于天数的动态规划：计算最多D天可处理的最大食物数
ll max_foods_dp(ll D, ll A, ll B) {
    if (D < A) {
        return 1; // 叶节点：只能处理1种食物
    }
    // 检查缓存，避免重复计算
    if (memo[D][A].count(B)) {
        return memo[D][A][B];
    }
    // 递归计算：左子树（无反应）+ 右子树（有反应）
    ll res = max_foods_dp(D - A, A, B) + max_foods_dp(D - B, A, B);
    memo[D][A][B] = res;
    return res;
}

// 闭式解：0条B边（线性）
ll linear(ll D, ll A, ll B) {
    return D / A + 1;
}

// 闭式解：1条B边（二次）
ll quadratic(ll D, ll A, ll B) {
    ll R = (D - B) / A;
    if (R <= 0) return linear(D, A, B);
    if (INF / R < R) return INF;
    return linear(D, A, B) + (R * (R + 1)) / 2;
}

// 闭式解：2条B边（三次）
ll cubic(ll D, ll A, ll B) {
    ll ans = quadratic(D, A, B);
    ll a = (D - 2 * B) / A;
    if (a <= 0) return ans;
    for (ll i = 0; i < a; ++i) {
        ll R = a - i;
        if (R <= 0) continue;
        if (INF / R < R) return INF;
        ans += (R * (R + 1)) / 2;
        if (ans > INF) return INF;
    }
    return ans;
}

// 二分查找：找到最小天数X使得func(X, A, B) >= N
ll binary_search(ll N, ll A, ll B, ll low, ll high, function<ll(ll, ll, ll)> func) {
    while (high - low > 1) {
        ll mid = (low + high) / 2;
        if (func(mid, A, B) >= N) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return high;
}

// 计算最少天数
ll min_days(ll N, ll A, ll B) {
    // 检查闭式解适用范围
    if (cubic(3 * B + A, A, B) + 1 >= N) {
        return binary_search(N, A, B, 3 * B + A, 51 * B, max_foods_dp);
    } else if (cubic(2 * B + A, A, B) >= N) {
        return binary_search(N, A, B, 2 * B + A, 3 * B + A, cubic);
    } else if (quadratic(B + A, A, B) >= N) {
        return binary_search(N, A, B, B + A, 2 * B + A, quadratic);
    } else {
        return binary_search(N, A, B, -1, B + A, linear);
    }
}

int main() {
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; ++t) {
        ll N, A, B;
        cin >> N >> A >> B;
        cout << "Case #" << t << ": " << min_days(N, A, B) << endl;
    }
    return 0;
}

题解：P13268 [GCJ 2014 Finals] Allergy Testing

文章操作

官方题解

基于食物数量的动态规划

基于天数的动态规划

cpp 解法由AI提供

相关推荐

评论

题解：P13268 [GCJ 2014 Finals] Allergy Testing

文章操作

官方题解

基于食物数量的动态规划

基于天数的动态规划

cpp 解法 由AI提供

相关推荐

评论

cpp 解法由AI提供