记录一道 GESP 2024年3月 的搜索真题。这类题在考试里属于必得分项，核心就那几行代码，关键是别在小细节上丢分。

题目来源：ACGO A81602 ｜ 2024年3月 六级
赛事场次：2024年3月 六级

一、题目信息

题目名称：游戏

赛事场次：2024年3月 六级

难度定位：六级

涉及知识点：动态规划 深度优先搜索

题目链接：https://www.acgo.cn/problemset/info/81602

坑点（这题失分基本都在这）

• 搜索状态定义；访问标记的置位与回溯；剪枝。
• 注意从题干中提取数据范围，它直接决定算法选择。
• 计数题要明确「什么算同一种」，避免重复或漏算。

题意简述

你有四个正整数 n,a,b,c，并准备用它们玩一个简单的小游戏。

在一轮游戏操作中，你可以选择将 n 减去 a，或是将 n 减去 b。游戏将会进行多轮操作，直到当 n ≤ c 时游戏结束。

你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将 n 减去 a，而另一种操作序列选择将 n 减去 b。如果 a=b，也认为将 n 减去 a 与将 n 减去 b 是不同的操作。

由于答案可能很大，你只需要求出答案对 1 000 000 007 取模的结果。

数据规模与约定

• 对 20% 的数据，a=b=c=1，n ≤ 30。
• 对 40% 的数据，c = 1，n ≤ 10³。
• 对全部的测试数据，保证 1 ≤ a,b,c ≤ n ≤ 2 × 10⁵。

前置知识

下面先把需要的基础知识理一遍，不熟悉的朋友可以跟着看，熟悉的直接跳过。

整数除法与取余：C++ 中两个整数相除结果仍是整数，小数部分直接舍去，例如 5/2 得到 2 而不是 2.5。要得到小数必须先把其中一个数转成 double。
取余运算：a % b 得到 a 除以 b 的余数，常用来判断整除关系，例如 n % 2 == 0 表示 n 是偶数。

二、思路分析

先看清楚题目要我们做什么

把题目读两遍，我们提取出关键信息：输入是什么、要输出什么、有哪些约束条件。这道题考查的是搜索，属于这类题里比较基础的一道，把题目要求一步步翻译成代码逻辑就能解决。

我的思考过程

读完题之后，我的第一反应是这样的：通过动态规划求解。f[N + i] 表示从 n 开始，经过若干操作后值为 i 的游戏操作序列数量。状态转移方程为 f[N + i - a] = (f[N + i - a] + f[N + i]) % mod; 和 f[N + i - b] = (f[N + i - b] + f[N + i]) % mod;，从 n 倒推到 c，最后累加 f 数组中 c 及以下的结果对 mod 取模。

需要说明的是，上面这个思路是把题目要求直译成代码得到的，没有用到什么高级技巧。对于这类基础题，读准题意加写对边界比追求巧妙解法更重要，因为考试里这种题是必须拿满分的。

三、完整代码 + 逐行注释

#include <cstdio>
 using namespace std;
 const int N = 2e5 + 5;
 const int mod = 1e9 + 7;
 int n, a, b, c;
 int f[N << 1];
 int ans;
 int main()
 {
    scanf("%d%d%d%d", &n, &a, &b, &c);
    f[N + n] = 1;
    for (int i = n; i > c; i--)  // 遍历
    {
        f[N + i - a] = (f[N + i - a] + f[N + i]) % mod;
        f[N + i - b] = (f[N + i - b] + f[N + i]) % mod;
    }
    for (int i = 0; i <= N + c; i++)  // 遍历
        ans = (ans + f[i]) % mod;
    printf("%d\n", ans);
    return 0;
 }

四、代码分段拆解

为了看得更清楚，我们把代码按功能分成几段解释。

第一步：引入头文件

#include <cstdio>
 using namespace std;

#include <iostream> 提供输入输出功能，using namespace std; 让我们能直接写 cin、cout 而不用加前缀。这两行是几乎所有 C++ 程序的开头，照写即可。

第二步：读入数据

    scanf("%d%d%d%d", &n, &a, &b, &c);

注意变量的类型要能装下题目的数据。本题数据范围到 10³，如果接近或超过 21 亿，就必须用 long long 而不是 int。

第三步：核心处理逻辑

    for (int i = n; i > c; i--)
    for (int i = 0; i <= N + c; i++)

这一段是整道题的关键，也是搜索的体现。看循环的三个要素：从哪里开始、什么时候结束、每次怎么变化。这三个要素任何一个写错，结果都会不对。

第四步：按要求输出

    printf("%d\n", ans);

输出格式必须和题目要求的完全一致。很多同学算法完全正确却因为少了一个换行或者空格多寡不对而 WA，这种分丢得最可惜。

五、实例模拟

光看代码可能还不够直观，我们用题目的样例实际跑一遍，看看程序是怎么走的。

以题目的第一组样例为例：

样例输入

1 1 1 1

样例输出

1

把这份输入代进代码，程序会先把数据依次读入，然后进入循环逐个判断，把满足条件的值累积起来，最后按格式输出。建议你对照着代码在纸上走一遍前两次循环，确认自己对每一步的理解都和程序一致。

题目另外还给了 2 组样例，做完之后建议把剩下的样例都跑一遍，全部通过再提交，能避开大部分边界问题。

六、踩坑总结

下面是做这道题时最容易出错的地方，对照自己的代码检查一下：

1. 变量类型不够用：题目数据范围较大，累加结果可能突破 21 亿，必须用 long long 声明累加变量，用 int 会溢出得到负数或错误值。
2. 取余与整除混淆：a % b 取的是余数，a / b 取的是整数商，两个完全不同。判断倍数关系用 a % b == 0，写成 a / b == 0 就全错了。
3. 循环起点搞错：题目说的是「正整数」，循环要从 1 开始而不是从 0 开始，差一个数就是 WA。
4. 输出格式不符：题目要求输出几行就输出几行，行末换行、数字之间的空格都要严格对齐，算法对了但格式错了同样判 WA，这种分丢得最冤。
5. 特殊情况没特判：把最小数据、最大数据、答案恰好等于 0 的情况各测一遍。特别是边界输入，出题人最喜欢在这里设陷阱。

七、知识点拓展

最后总结一下这道题带给我们的通用经验：

• 本题考查搜索的基本写法，这类题在考试中属于必得分项，要练到能默写。
• 写完代码后建议自己造几组边界数据测试，特别是最小值和最大值。
• 同一知识点在不同场次反复出现，把这道题的写法吃透，后面遇到同类题可以直接套用。

八、适用人群

如果你已经掌握搜索的基本写法，这道题可以用来巩固手感。

这道题就讲到这里。我会持续更新各场次真题的详细拆解，需要系统复习的同学可以关注这个系列。有问题欢迎评论区讨论。