GESP 2024年3月 真题 游戏 完整题解(搜索)
- 2026-11-21 17:40:40
你有四个正整数 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⁵。
换个角度看这题:如果你是出题人,你会怎么设卡?顺着这个角度,解法反而更好记。
轮到 GESP 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。
一句话概括:用动态规划 深度优先搜索把题目要求原样翻译成代码,属于考场上必须拿满分的题。
| 卡点 | 出题人卡的是什么 | 你要做的事 |
|---|---|---|
| 数据类型 | 用 int 装不下的人 | 累加变量用 long long |
| 边界 | 只按样例想问题的人 | 数据从 1 开始编号 |
| 输出格式 | 不看输出要求直接 cout 的人 | 换行、空格、顺序逐项对 |
三个卡点都不难,难的是同时想到。
出题人不会白给数据范围。范围里就藏着「能不能暴力」这个提示,顺着它往回推,解法基本就定了。
通过动态规划求解。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 取模。
建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。
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;
}
逐段过一遍会太啰嗦,我只讲决定对错的那两段。
第一段,把数据读进来。
f[N + n] = 1;
读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。
第二段,核心处理。
{
f[N + i - a] = (f[N + i - a] + f[N + i]) % mod;
f[N + i - b] = (f[N + i - b] + f[N + i]) % mod;
}
这段是整道题唯一需要想的地方,也是搜索的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。
验证不是随便点几下提交,按下面的清单走一遍。
样例输入
样例输出
| 步骤 | 做什么 | 通过标准 |
|---|---|---|
| 1 | 跑题目给的样例 | 输出和样例逐字符一致,包括空格和换行 |
| 2 | 试最小的输入 | 只给一个数、只给一行,程序不崩也不越界 |
| 3 | 按上限造一组数据 | 耗时在 1 秒内,答案不溢出 |
| 4 | 检查取模结果 | 不会出现负数 |
| 5 | 检查输出末尾 | 没有多余空格,最后一行有换行 |
题目还有 2 组样例,全部跑通再提交。
按危险程度从高到低排,第一条最常见:
- 取模后成负数——写成
(a - b) % p直接输出 就错,应该是((a - b) % p + p) % p。 - 累加结果溢出——写成
int sum = 0;就错,应该是 累加变量用long long。 - 下标起点错位——写成
for (i = 0; i < n; i++)存a[i]就错,应该是for (i = 1; i <= n; i++)存a[i]。 - 输出格式不符——写成
cout << ans;就错,应该是cout << ans << "\n";。 - 多组数据没清空——写成 全局数组直接用 就错,应该是 每组数据前
memset或重新赋值。
总结一下,下次遇到同类题你只需要回忆这三点。
- 筛的是什么:动态规划 深度优先搜索的完整度——范围、边界、格式缺一不可。
- 要记住的:搜索完一个分支,把改过的标记改回去,否则后面的分支会看到脏数据。
- 下一步:找同场次另一道题,用同样的三个卡点自查一遍。
下一篇继续同场次的真题。有更短的写法,欢迎评论区贴出来。
- 本文属于《GESP 真题题解》系列,第 70 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
- 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
- 想跟完整系列的朋友点个关注,更新会第一时间推送。
- 本系列合集目录(按年份/组别排序)
GESP 的坑多半在边界和读题上。这道搜索题把该注意的点都列在上面的表里了,提交前逐条过一遍。
今天想问你:如果让你给这题改一个数据,让暴力刚好过不了,你会怎么改?
顺手点个 赞,你的反馈决定我先把哪个专题更完;关注之后,每天的新题解会自动找上门。
想要这题的可运行代码文件?后台回复 “资料” 直接拿。
本篇编号 GESP-078(公众号 MP-078)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。