【CSP】CSP-XL 2025辽宁复赛真题-第四题, 购物（buy）

CSP-XL 2025辽宁复赛真题-第四题，购物（buy），也是本次考试最后一题，难度最大，DFS思想考点，属于GESP六级考纲内容，难度⭐⭐⭐☆☆。

CSP-XL 2025辽宁复赛真题-第四题, 购物（buy）

题目要求

---

题目分析

1.问题抽象

这是一个组合计数问题，本质是：

• 决策树问题：每个物品是一个决策点，每个决策点有 2 个分支
• 状态空间搜索：需要遍历所有可能的组合状态
• 约束满足问题：在满足 sum ≤ s 的约束下计数

2.问题特征识别

当我们看到以下特征时，应该考虑DFS回溯：

1. ✅ 需要枚举所有可能的组合/排列
2. ✅ 每个位置有多个选择
3. ✅ 需要统计满足条件的方案数
4. ✅ 数据规模相对较小

3.思维模型：决策树

想象一棵决策树：

                    [开始: sum=0]
                    /            \
         [选物品1选项0: sum=2]    [选物品1选项1: sum=3]
            /          \              /          \
    [选物品2选项0] [选物品2选项1] [选物品2选项0] [选物品2选项1]
    sum=3 ✓        sum=6 ✗        sum=4 ✓        sum=7 ✗

关键理解：

• 每个节点代表一个状态（当前已做的选择）
• 每条边代表一个决策（选择哪个选项）
• 叶子节点代表一个完整方案

4.算法的三个核心步骤

步骤1：尝试（Make Choice）

sum += a[count][i];  // 做出选择：累加当前选项的值

• 在当前决策点，尝试一个选项
• 更新状态（sum）

步骤2：递归（Recurse）

dfs(count + 1);  // 递归处理下一个决策点

• 基于当前选择，继续处理后续决策
• 这是分治思想：把大问题分解为子问题

步骤3：回溯（Undo Choice）

sum -= a[count][i];  // 撤销选择：恢复状态

• 撤销当前选择，恢复状态
• 准备尝试下一个选项

4.完整执行示例

假设 n=2, s=5，数据：

• 物品1: [2, 3]
• 物品2: [1, 4]

执行流程：

调用栈和状态变化：

1. dfs(0) - count=0, sum=0
   ├─ 尝试选项0: sum = 0 + 2 = 2
   │  └─ dfs(1) - count=1, sum=2
   │     ├─ 尝试选项0: sum = 2 + 1 = 3
   │     │  └─ dfs(2) - count=2, sum=3
   │     │     └─ 终止条件：count == n
   │     │        └─ 检查：sum=3 ≤ 5 ✓，ans++ (ans=1)
   │     │     └─ 返回
   │     │  └─ 回溯：sum = 3 - 1 = 2
   │     │
   │     └─ 尝试选项1: sum = 2 + 4 = 6
   │        └─ dfs(2) - count=2, sum=6
   │           └─ 终止条件：count == n
   │              └─ 检查：sum=6 > 5 ✗，不计数
   │           └─ 返回
   │        └─ 回溯：sum = 6 - 4 = 2
   │     └─ 返回
   │  └─ 回溯：sum = 2 - 2 = 0
   │
   └─ 尝试选项1: sum = 0 + 3 = 3
      └─ dfs(1) - count=1, sum=3
         ├─ 尝试选项0: sum = 3 + 1 = 4
         │  └─ dfs(2) - count=2, sum=4
         │     └─ 终止条件：count == n
         │        └─ 检查：sum=4 ≤ 5 ✓，ans++ (ans=2)
         │     └─ 返回
         │  └─ 回溯：sum = 4 - 1 = 3
         │
         └─ 尝试选项1: sum = 3 + 4 = 7
            └─ dfs(2) - count=2, sum=7
               └─ 终止条件：count == n
                  └─ 检查：sum=7 > 5 ✗，不计数
               └─ 返回
            └─ 回溯：sum = 7 - 4 = 3
         └─ 返回
      └─ 回溯：sum = 3 - 3 = 0
   └─ 返回

最终：ans = 2

---

记住：DFS回溯的本质是系统性地尝试所有可能，通过回溯保证不遗漏、不重复。

---

示例代码

#include <iostream>
long long a[25][2];      // a[i][0] 表示第 i 件物品方案一的花费，a[i][1] 表示方案二的花费
long long sum = 0;       // 当前已选物品的总花费
long long n, S;          // n 件物品，预算上限为 S
long long ans = 0;       // 记录总花费不超过 S 的合法方案数

// 深度优先搜索，count 表示当前正在决策第 count 件物品（0-based）
void dfs(int count) {
    if (count == n) {               // 所有物品决策完毕
        if (sum <= S) {             // 若总花费不超预算，则方案合法
            ans++;
        }
        return;
    }
    // 对第 count 件物品，分别尝试“不选”与“选”两种选择
    for (int i = 0; i <= 1; i++) {
        sum += a[count][i];         // 累加当前选择的花费
        dfs(count + 1);             // 递归决策下一件物品
        sum -= a[count][i];         // 回溯，撤销当前选择的花费
    }
    return;
}

int main() {
    freopen("buy.in", "r", stdin);   // 按复赛要求重定向输入
    freopen("buy.out", "w", stdout); // 按复赛要求重定向输出
    std::cin >> n >> S;              // 读入物品件数 n 与预算上限 S

    for (int i = 0; i < n; i++) {
        std::cin >> a[i][0] >> a[i][1]; // 读入每件物品不选/选的花费
    }

    dfs(0);                          // 从第 0 件物品开始搜索

    std::cout << ans;                // 输出合法方案总数
    return 0;
}

---

附：样例和测试数据下载地址：

链接：https://pan.quark.cn/s/51ac09b0b260?pwd=DRDt 提取码：DRDt

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号