ARTICLE · 1370797
GESP 2024年12月 真题 Recamán 完整题解(递推)
小杨最近发现了有趣的 Recaman 数列, 这个数列是这样生成的:
· 数列的第一项a₁是1;
· 如果aₖ₋₁-k是正整数并且没有在数列中出现过,那么数列的第k项aₖ为aₖ₋₁-k,否则为aₖ₋₁+k。
小杨想知道 Recaman 数列的前n项从小到大排序后的结果。手动计算非常困难,小杨希望你能帮他解决这个问题。
这题有两种写法:一种三分钟能写对但过不了大数据,一种要想一会儿但能拿满分。两种都讲。
今天刷 GESP 2024年12月 的这道递推题。先说结论:思路只有一句话,难的是把这句话不折不扣地落成代码。
题目:Recamán
场次:2024年12月 四级|难度:四级
知识点:递推
链接:https://www.acgo.cn/problemset/info/46124
小杨最近发现了有趣的 Recaman 数列, 这个数列是这样生成的: · 数列的第一项a₁是1; · 如果aₖ₋₁-k是正整数并且没有在数列中出现过,那么数列的第k项aₖ为aₖ₋₁-k,否则为aₖ₋₁+k。 小杨想知道 Recaman 数列的前n项从小到大排序后的结果。手动计算非常困难,小杨希望你能帮他解决这个问题。
一句话概括:用递推把题目要求原样翻译成代码,属于考场上必须拿满分的题。
| 初版(只想让样例过) | 定稿(能拿满分) | |
|---|---|---|
| 数据类型 | int 一把梭 | 累加变量用 long long |
| 边界 | 只试样例那组 | 题目说「到」或者「包括」 |
| 输出 | cout << ans; | 按题目要求补换行与空格 |
初版和定稿的算法是同一个,差的只是这三处。
先看初版怎么想:把题面逐句翻译,能跑样例就算完。这条路能拿到分,但只在小数据上。
已知前面的项和递推公式,按照递推的思想循环依次求出后面的项,再排序后即可得到结果。 因为递推公式中有"数是否出现过"的判断,所以需要有数组记录是否出现过,可以用int类型或bool类型来进行标记,初始值为0或false表示未出现过,出现之后改为1或True。 这个标记数组稍微大一些即可,3000项计算的结果为五位数。
两条路的分岔点只有一个:动笔前有没有先算一遍账。
建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int n; scanf("%d", &n);
int a[3005]; bool vis[500005] = {false};
a[0] = 1; vis[1] = true;
for (int i = 1; i < n; i++) { // 遍历
int t = a[i - 1] - (i + 1);
if (t > 0 && !vis[t]) a[i] = t; // 判断
else a[i] = a[i - 1] + (i + 1);
vis[a[i]] = true;
}
sort(a, a + n);
for (int i = 0; i < n; i++) printf("%d ", a[i]); // 遍历
return 0;
}
代码在上面,这里只挑最关键的两段讲,其他都是顺手写的。
第一段,把数据读进来。
int a[3005]; bool vis[500005] = {false};
a[0] = 1; vis[1] = true;
读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。
第二段,核心处理。
int t = a[i - 1] - (i + 1);
if (t > 0 && !vis[t]) a[i] = t;
else a[i] = a[i - 1] + (i + 1);
vis[a[i]] = true;
}
这段是整道题唯一需要想的地方,也是递推的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。
下面按四步验一遍,这个顺序建议你考试时也照做。
样例输入
样例输出
| 步骤 | 做什么 | 通过标准 |
|---|---|---|
| 1 | 把第一组样例抄进去跑 | 一个字都不差,行尾空格也别多 |
| 2 | 换成最小规模 | n = 1 或只有一组数据时不崩,结果符合题意 |
| 3 | 看最后一行 | 结尾有换行,不多输出空行 |
| 4 | 跑完剩下 1 组样例 | 全部对上再提交,别只看第一组 |
题目还有 1 组样例,全部跑通再提交。
按危险程度从高到低排,第一条最常见:
- 排序方向写反——写成
sort(a, a+n)想降序却用了默认升序 就错,应该是 降序要写sort(a, a+n, greater<int>())。 - 累加结果溢出——写成
int sum = 0;就错,应该是 累加变量用long long。 - 漏掉区间右端点——写成
i < R就错,应该是i <= R。 - 下标起点错位——写成
for (i = 0; i < n; i++)存a[i]就错,应该是for (i = 1; i <= n; i++)存a[i]。 - 输出格式不符——写成
cout << ans;就错,应该是cout << ans << "\n";。
最后收个尾,三句话说完这题。
- 两个版本的差别:算法相同,差在类型、边界、输出三处。
- 要记住的:递推的第一项、第二项要手算确认,初值错了整张表都是错的。
- 下一步:下一题动笔前先花两分钟算范围和边界。
系列按场次往前推,下一篇还在这个级别,难度会往上走一档。
- 本文属于《GESP 真题题解》系列,第 20 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
- 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
- 想跟完整系列的朋友点个关注,更新会第一时间推送。
- 本系列合集目录(按年份/组别排序)
GESP 的坑多半在边界和读题上。这道递推题把该注意的点都列在上面的表里了,提交前逐条过一遍。
今天想问你:如果把这题的数据范围扩大 10 倍,你的写法还撑得住吗?评论区聊聊你会怎么改。
有用就收藏一份,考前翻出来快速过一遍错题点;关注本号,真题系列每天不间断。
真题代码包和更新排期都放在后台了,回复 “资料” 两个字自取。
本篇编号 GESP-052(公众号 MP-052)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。















































































