B4068 [GESP202412 四级] Recamán

欢迎报名洛谷网校，期待和大家一起进步！

本题考查桶思想和排序。

根据题目含义，先求出 Recamán 数列，使用数组

a

进行存储。在求 Recamán 数列的时候，重点在于如何处理【没有在数列中出现过】。这里采用桶思想，定义数组 vis，如果 vis[x] == 1，说明

x

这个数已经出现过了，否则没有出现过。至于 vis 数组应该开多少，后面会详细讨论这个问题。

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

CPP

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

，因此可以任意选择一种排序方式，例如选择排序、冒泡排序都是可以使用的。这里提供一个选择排序的参考代码：

CPP

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 数组的大小会是一个天文数字。

B4068 [GESP202412 四级] Recamán

文章操作

相关推荐

评论

B4068 [GESP202412 四级] Recamán