夜雨聆风学习资料网

ARTICLE · 1370797

GESP 2024年12月 真题 Recamán 完整题解(递推)

GESP 2024年12月 真题 Recamán 完整题解(递推)
【GESP 2024年12月 真题 Recamán 完整题解(递推)】
题目描述

小杨最近发现了有趣的 Recaman 数列, 这个数列是这样生成的:
· 数列的第一项a₁是1;
· 如果aₖ₋₁-k是正整数并且没有在数列中出现过,那么数列的第k项aₖ为aₖ₋₁-k,否则为aₖ₋₁+k。

小杨想知道 Recaman 数列的前n项从小到大排序后的结果。手动计算非常困难,小杨希望你能帮他解决这个问题。

样例 1
输入
5
输出
1 2 3 6 7
样例 2
输入
8
输出
1 2 3 6 7 12 13 20
题解正文

这题有两种写法:一种三分钟能写对但过不了大数据,一种要想一会儿但能拿满分。两种都讲。

今天刷 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项计算的结果为五位数。

先排序 → 读入数据 → 逐个处理(递推的核心逻辑) → 按格式输出

两条路的分岔点只有一个:动笔前有没有先算一遍账。

四、正解代码

建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。

// Recaman 数列:按递推生成,再排序输出
#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 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;
    }

这段是整道题唯一需要想的地方,也是递推的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。

六、用样例核对两种写法

下面按四步验一遍,这个顺序建议你考试时也照做。

样例输入

5

样例输出

1 2 3 6 7
步骤做什么通过标准
1把第一组样例抄进去跑一个字都不差,行尾空格也别多
2换成最小规模n = 1 或只有一组数据时不崩,结果符合题意
3看最后一行结尾有换行,不多输出空行
4跑完剩下 1 组样例全部对上再提交,别只看第一组

题目还有 1 组样例,全部跑通再提交。

七、优化时最容易写错的地方

按危险程度从高到低排,第一条最常见:

  1. 排序方向写反——写成 sort(a, a+n) 想降序却用了默认升序 就错,应该是 降序要写 sort(a, a+n, greater<int>())。
  2. 累加结果溢出——写成 int sum = 0; 就错,应该是 累加变量用 long long。
  3. 漏掉区间右端点——写成 i < R 就错,应该是 i <= R。
  4. 下标起点错位——写成 for (i = 0; i < n; i++) 存 a[i] 就错,应该是 for (i = 1; i <= n; i++) 存 a[i]。
  5. 输出格式不符——写成 cout << ans; 就错,应该是 cout << ans << "\n";。
八、这题的取舍

最后收个尾,三句话说完这题。

  • 两个版本的差别:算法相同,差在类型、边界、输出三处。
  • 要记住的:递推的第一项、第二项要手算确认,初值错了整张表都是错的。
  • 下一步:下一题动笔前先花两分钟算范围和边界。

系列按场次往前推,下一篇还在这个级别,难度会往上走一档。


系列导航
  • 本文属于《GESP 真题题解》系列,第 20 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
  • 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
  • 想跟完整系列的朋友点个关注,更新会第一时间推送。
  • 本系列合集目录(按年份/组别排序)
写在最后

GESP 的坑多半在边界和读题上。这道递推题把该注意的点都列在上面的表里了,提交前逐条过一遍。

今天想问你:如果把这题的数据范围扩大 10 倍,你的写法还撑得住吗?评论区聊聊你会怎么改。

有用就收藏一份,考前翻出来快速过一遍错题点;关注本号,真题系列每天不间断。

真题代码包和更新排期都放在后台了,回复 “资料” 两个字自取。

本篇编号 GESP-052(公众号 MP-052)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料