这是一个用来生成 B4068 [GESP202412 四级] Recamán 题目测试数据的完整 C++ 代码。

该代码会生成 10 组测试数据（1.in/1.out 到 10.in/10.out）。测试点设计覆盖了题目要求的各类情况：

1. 边界情况：$n=1$（最小值）和 $n=3000$（最大值）。
2. 样例验证：包含了题目描述中的两个样例（$n=5$ 和 $n=8$）。
3. 规模递增：涵盖了小规模（几十）、中规模（几百）到大规模（几千）的数据，确保全面测试。

数据生成器代码 (generator.cpp)

你可以将以下代码保存为 generator.cpp，编译并运行。它将在当前目录下生成所有的输入输出文件。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 估算最大值：最坏情况是一直做加法，1 + 2 + ... + 3000 ≈ 4,500,000
// 5,000,000 足够安全，且 vector<bool> 占用内存极小
const int MAX_VAL_LIMIT = 5000005;

// 核心解题逻辑与文件生成
void generate_case(int id, int n) {
    // --- 1. 生成输入文件 (.in) ---
    string in_filename = to_string(id) + ".in";
    ofstream fin(in_filename);
    fin << n << endl;
    fin.close();

    // --- 2. 生成输出文件 (.out) ---
    string out_filename = to_string(id) + ".out";
    ofstream fout(out_filename);

    // 使用 vector<bool> 记录数字是否出现过
    // 每次调用函数重新分配，保证状态清空
    vector<bool> visited(MAX_VAL_LIMIT, false);
    vector<int> a;
    a.reserve(n);

    // 第一项是 1
    int current = 1;
    a.push_back(current);
    visited[current] = true;

    // 按照题目规则生成后续项
    for (int k = 2; k <= n; ++k) {
        int next_val_sub = current - k;
        
        // 规则：如果减去 k 后的数大于 0 且未出现过，则减；否则加
        if (next_val_sub > 0 && !visited[next_val_sub]) {
            current = next_val_sub;
        } else {
            current = current + k;
        }
        
        a.push_back(current);
        visited[current] = true;
    }

    // 题目要求：从小到大排序
    sort(a.begin(), a.end());

    // 输出结果，用空格分隔
    for (int i = 0; i < n; ++i) {
        fout << a[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();

    cout << "Generated Test Case " << id << ": n = " << n << endl;
}

int main() {
    // 1. 最小边界
    generate_case(1, 1);
    
    // 2. 题目样例 1
    generate_case(2, 5);
    
    // 3. 题目样例 2
    generate_case(3, 8);
    
    // 4. 小规模数据
    generate_case(4, 50);
    
    // 5. 中等规模数据
    generate_case(5, 200);
    
    // 6. 中等规模数据
    generate_case(6, 500);
    
    // 7. 大规模数据
    generate_case(7, 1000);
    
    // 8. 大规模数据
    generate_case(8, 2000);
    
    // 9. 接近最大边界
    generate_case(9, 2500);
    
    // 10. 最大边界
    generate_case(10, 3000);

    return 0;
}

使用方法

1. 将上述代码保存为 generator.cpp。
2. 使用 C++ 编译器编译：g++ generator.cpp -o generator。
3. 运行生成的可执行文件：./generator（Windows 下为 generator.exe）。
4. 运行结束后，当前目录下会出现 1.in ~ 10.in 和 1.out ~ 10.out 共 20 个文件。

测试点覆盖说明

• 测试点 1: $n=1$，测试最小输入的边界情况。
• 测试点 2-3: $n=5, 8$，对应题目描述中的样例，确保基础逻辑正确。
• 测试点 4-6: $n=50, 200, 500$，测试中小规模数据的生成和排序正确性。
• 测试点 7-9: $n=1000, 2000, 2500$，测试较大规模数据，验证 visited 数组大小是否足够以及算法效率。
• 测试点 10: $n=3000$，题目给定的最大数据范围，确保在极限情况下程序不崩溃、不超时且结果正确。

这是一个经典的模拟与排序题目。我们需要按照题目给定的规则生成数列的每一项，然后对生成好的数列进行排序输出。

题目分析

1. 生成规则：

   • 第 $1$ 项 $a_1 = 1$。
   • 对于第 $k$ 项（$k \ge 2$），我们需要根据前一项 $a_{k-1}$ 来计算：
     • 先计算尝试值 $val = a_{k-1} - k$。
     • 判断条件：如果 $val > 0$ 且 $val$ 在之前没有出现过，那么 $a_k = val$。
     • 否则（$val \le 0$ 或 $val$ 已经出现过），$a_k = a_{k-1} + k$。

2. 判断“是否出现过”：

   • 我们需要在生成过程中快速知道一个数字是否已经存在于数列中。
   • 由于 $n$ 最大为 $3000$，数列中的最大值大概在 $1 + 2 + \dots + 3000 \approx \frac{3000^2}{2} \approx 4.5 \times 10^6$ 左右。
   • 我们可以使用一个布尔数组 visited（或者叫标记数组）来记录数字是否出现过。visited[x] = true 表示数字 $x$ 已经存在。数组大小开到 $5 \times 10^6$ 即可满足需求，内存占用约 5MB，完全在允许范围内。
   • 如果不想使用大数组，鉴于 $n$ 较小，也可以在每次生成时遍历前面的元素进行查找（时间复杂度 $O(n^2)$），对于 $n=3000$ 也是可以通过的。但使用布尔数组的方法（时间复杂度 $O(n)$）更高效且通用。

3. 排序：

   • 生成完 $n$ 个数后，使用 std::sort 对数组进行从小到大排序。

4. 输出：

   • 按顺序输出排序后的数组，数字之间用空格分隔。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 估算最大值：最坏情况是一直做加法，1 + 2 + ... + 3000 ≈ 4,500,000
// 开一个 5,000,005 的布尔数组来标记数字是否出现过
// 全局变量自动初始化为 false
const int MAX_VAL = 5000005;
bool visited[MAX_VAL];

int main() {
    // 优化输入输出效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> a;
    a.reserve(n); // 预分配内存

    // 第一项是 1
    int current = 1;
    a.push_back(current);
    visited[current] = true;

    // 从第 2 项开始计算到第 n 项
    // 注意题目描述中的 k 对应这里的循环变量
    for (int k = 2; k <= n; ++k) {
        int next_val_sub = current - k;
        
        // 判断条件：是正整数 且 没有出现过
        if (next_val_sub > 0 && !visited[next_val_sub]) {
            current = next_val_sub;
        } else {
            current = current + k;
        }
        
        // 将新生成的项加入数列并标记
        a.push_back(current);
        visited[current] = true;
    }

    // 题目要求输出排序后的结果
    sort(a.begin(), a.end());

    // 输出
    for (int i = 0; i < n; ++i) {
        cout << a[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

样例 1 模拟过程 ($n=5$)

1. $k=1$: $a_1 = 1$, 标记 vis[1]=true。目前数列: [1]。
2. $k=2$: $1 - 2 = -1$ (不是正整数)。执行加法: $1 + 2 = 3$。$a_2 = 3$, 标记 vis[3]=true。目前数列: [1, 3]。
3. $k=3$: $3 - 3 = 0$ (不是正整数)。执行加法: $3 + 3 = 6$。$a_3 = 6$, 标记 vis[6]=true。目前数列: [1, 3, 6]。
4. $k=4$: $6 - 4 = 2$ (是正整数且未出现过)。执行减法。$a_4 = 2$, 标记 vis[2]=true。目前数列: [1, 3, 6, 2]。
5. $k=5$: $2 - 5 = -3$ (不是正整数)。执行加法: $2 + 5 = 7$。$a_5 = 7$, 标记 vis[7]=true。目前数列: [1, 3, 6, 2, 7]。

生成结束，排序后为 1 2 3 6 7，与样例输出一致。