WFYZ 暑期 CSP-S 模拟训练 2 —— 解题报告

本卷共 4 题，均以 C++14 为标程标准（g++ -std=c++14 -O2 编译，已本机实测通过）。 覆盖 背包 DP（多维/计数）、贪心排序 + DP、数位计数/分段多项式求和 等高阶题型。 难度梯度为 普及+/提高- 到 提高+/省选-，适合 CSP-S 暑期冲刺。

题目总览

各题要点与易错提醒

A. 运输金子（背包 DP + 端点外挂）

• 转化：每根金条重心必须在容器内，因此除最左、最右各一根可有一半露在外，其余必须完全在容器内。长度乘 2 后容量变 2L：完整放入占 2aᵢ，端点外挂只占 aᵢ 且最多 2 根。
• 做法：dp[t][j] = 已外挂 t 根、占用长度 j 的最大价值，0-1 背包转移。
• 易错：单根金条重心放容器正中、两侧都能外挂，任何长度都放得下，答案初值要取 max(vᵢ)；价值用 long long。

B. 土豆先生（背包 DP + 凸性）

• 转化：P₁·P₂ = C₁(C−C₁) / (A₁(A−A₁))，固定 A₁ 时分子关于 C₁ 开口向下，最小值在 C₁ 极值处。
• 做法：背包 DP 同时求「恰好 L 袋、土豆总数 w」时总价的最小值和最大值，两个极值各试一次。
• 易错：输出保留 3 位小数，建议用整数运算精确舍入（scaled = floor(2000·C₁·C₂ + w(A−w)) / (2w(A−w))），避免浮点误差。

C. 四方配额（计数 + 分段多项式求和）

• 转化：a+c>b+d 且 a+d≥b+c ⟺ a>b 且 −(a−b) < c−d ≤ a−b。
• 做法：答案 = Σ f(k)·h(k)，f(k)=min(B,A−k)+1，h(k)=G(k)−G(−k)，G(t)=#{c−d≤t} 可用闭式 O(1) 求。f、G 都是分段低次多项式，在 O(1) 个区间上做多项式求和。
• 易错：G(k) 含半整系数（/2），求和时需用模逆 inv2；断点要取全（A−B+1、C、C−D+1、D+1、D−C+1），答案取模 10⁹+7。

D. 项目经验（贪心排序 + 背包 DP）

• 转化：同段内按 a/b 从大到小执行；总收入 = Σ bᵢ·(前缀 a 和 + [训练营后]·X)。
• 做法：按 a/b 从小到大处理项目，枚举 targetB（训练营后项目 b 之和），DP dp[j][k] 表示已放训练营后 j 个、b 之和为 k 的最大贡献。
• 易错：转移两分支（训练营前 / 后）的贡献公式要区分「已处理同段项目」；bᵢ≤10、Σb≤500 是 DP 状态可行的关键；本题为文件输入输出（money.in / money.out）。

训练建议

• A、B 是背包 DP 的变形，属于 CSP-S 必会考点，应优先吃透；尤其注意「端点外挂」「凸性取极值」这类建模转化。
• C 题重在把不等式约束转化为两个差值的区域，再用闭式 + 分段求和，是省选常见计数套路；做不出来属正常，重点是理解 G(t) 的闭式与分段求和思想。
• D 题的「同段排序 + 枚举划分 + 背包」是经典的排序 + DP 组合，建议结合 a/b 排序结论与贡献拆解反复理解。

数据与标程说明

• 每题提供 16~20 组测试数据 data1.in / data1.ans …，按子任务梯度分布（详见各题 README 子任务表）。
• 标程统一 C++14，g++ -std=c++14 -O2 编译，已本机实测：全部 68 组数据与官方/修正样例均通过。
• data/ 目录下 data_maker.py 为数据生成器，solver_ref.py 为 Python 参考求解器（与 C++ 标程交叉验证一致）。
• D 题样例修正说明：原题提供的 3 组样例中 X 值存在笔误（样例 1 的 18 应为 10、样例 2 的 108 应为 100、样例 3 输出 22696 应为 22288），本卷 README 已修正为与题解算法一致的自洽样例。