B4068 [GESP202412 四级] Recamán

chen_zhe · 2024-12-14 14:54:22 · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

本题考查桶思想和排序。

根据题目含义，先求出 Recamán 数列，使用数组 a 进行存储。在求 Recamán 数列的时候，重点在于如何处理【没有在数列中出现过】。这里采用桶思想，定义数组 vis，如果 vis[x] == 1，说明 x 这个数已经出现过了，否则没有出现过。至于 vis 数组应该开多少，后面会详细讨论这个问题。

因此我们可以写出下列计算 Recamán 数列的代码：

a[1] = vis[1] = 1;
for (int i = 2; i <= n; i++) {
    if (a[i - 1] - i >= 1 && !vis[a[i - 1] - i])
        a[i] = a[i - 1] - i;
    else
        a[i] = a[i - 1] + i;
    vis[a[i]] = 1;
}

题目要求输出 Recamán 数列从小到大排序后的结果。由于数据范围中 n\leq 3000，因此可以任意选择一种排序方式，例如选择排序、冒泡排序都是可以使用的。这里提供一个选择排序的参考代码：

for (int i = 1; i <= n; i++) {
    int mx = a[i], id = i;
    for (int j = i + 1; j <= n; j++) {
        if (a[j] < mx) {
            mx = a[j];
            id = j;
        }
    }
    swap(a[i], a[id]);
}

最后我们研究这个问题：记录这个数是否出现过的 vis 数组应该开多大呢？可以先将 vis 数组开得足够大（例如：900 万），然后运行整个程序，输入 3000，可以看到最大的输出数字为 11339。因此，vis 数组不需要开的非常大，只需开到 11340 即可。

实际上使用简单的数学推理即可得出，vis 数组肯定不需要开得很大。首先，只有执行加法时，最大值才会更新。假设一种最坏的情况（且是必然不可能出现的情况）：每一步都是执行加法，那么数列的第 n 项的值是 1+2+3+\dots+n=\dfrac{n(n+1)}{2}，代入 n=3000 得到结果为 4501500。这是一个相当宽松的上界，实际上，由于定义中优先选择减法生成新项，这会显著减缓数列的增长速度。总而言之，无需担心 vis 数组的大小会是一个天文数字。