真题选做

tder · 2025-03-31 23:31:54 · 题解

P5662 [CSP-J2019] 纪念品，*绿。

CSP-J 2019 T3。

有 N 个物品，第 i 个物品在第 j 天的价格为 p_{i,j}。每天可以买卖任意物品。初始有 M 块钱，求 T 天后能获得的最大收益。

考虑以下两种情形是等价的：

• 将某件物品在第 a 天买入，第 b 天卖出；
• 将某件物品在第 a 天买入，第 a+1 天卖出，第 a+1 天买入，第 a+2 天卖出，以此类推，第 b-1 天买入，第 b 天卖出。

因此，我们可以将每天分别考虑，强制第二天早上必须将所有物品卖出即可。对于第 i 天，考虑一个 dp，令 f_{j,k} 表示考虑到第 j 个物品有 k 块钱的最大收益，则：

同时，我们需要维护一个 q_i 表示第 i 天早上卖出所有物品后拥有的钱数，则：

使用背包技巧，容易发现 dp 其实只用存最后一维即可。

时间复杂度 \mathcal{O}(TNM)。

Code.

P5663 [CSP-J2019] 加工零件，*绿。

CSP-J 2019 T4。

有 n 个点 m 条边的图。q 组询问：给定 a,L，询问是否存在 1\sim a 的长为 L 的路径。

由于可以重复走某条边，显然的，若存在 1\sim a 的长为 L-2 的路径，那么一定存在长为 L 的路径。为了达到这一点，我们只需要重复走其中的某一条边即可。更进一步的，所有奇偶性相同的 L 的答案必定是相同的。

因此，我们不妨预处理出 1\sim i 的长为奇数的最短路径长度 p_i，以及 1\sim i 的长为偶数的最短路径长度 q_i。询问时：

• 若 L 为奇数，只需 L\ge p_i 即存在；
• 若 L 为偶数，只需 L\ge q_i 即存在。

具体实现时，可将每个点拆成 i 和 i+n，分别表示。