G4013 [GESP202412 四级] Recamán 题解

知识点：递推、集合、排序。

解题思路

从1开始生成，第k项优先取上一项-k；若结果不正或已经出现，则改取上一项+k。用集合记录出现值，生成完再排序输出。

为什么正确

集合保持此前出现值，分支判断恰落实递推优先级，因此生成序列正确；排序只用于最终输出。

易错点

不能在生成过程中排序，否则丢失上一项；回退条件包括0。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a= {
        1
    }
    ;
    set<int>s= {
        1
    }
    ;
    for(int k=2;k<=n;k++) {
        int x=a.back()-k;
        if(x<=0||s.count(x))x=a.back()+k;
        a.push_back(x);
        s.insert(x);
    }
    sort(a.begin(),a.end());
    for(int x:a)cout<<x<<" ";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。