这是一个标准的数据生成器。它结合了正确的解题逻辑（用于生成标准答案 .out）和针对不同测试点设计的输入数据生成逻辑（用于生成 .in）。

数据生成器功能说明

• 全自动生成：运行一次代码，即可在当前目录下生成 1.in/1.out 到 10.in/10.out 共20个文件。
• 覆盖全面：
  • 测试点 1-3：覆盖基础边界情况 ($N=1, 2, 3$)，检验递归基准。
  • 测试点 4-6：覆盖中等规模 ($N \le 30$)，检验基础递推逻辑。
  • 测试点 7-8：覆盖整数溢出临界区 ($N \approx 36$)，如果选手没开 long long，这几个点开始会挂。
  • 测试点 9-10：覆盖题目最大边界 ($N=60$)，必须使用 long long，检验算法效率和数值范围。

C++ 数据生成器代码

/**
 * P10250 [GESP样题 六级] 下楼梯 - 数据生成器
 * 功能：自动生成 1.in/1.out ~ 10.in/10.out
 * 作者：OI教练
 */

#include <iostream>
#include <fstream>   // 用于文件读写
#include <string>    // 用于文件名处理
#include <vector>
#include <cstdlib>   // 用于rand()
#include <ctime>     // 用于time()

using namespace std;

// ==========================================
// Part 1: 标准题解逻辑 (用于生成 .out)
// ==========================================

// 使用 long long 防止溢出
long long dp[70];

long long solve(int n) {
    // 每次计算前先清空或重新初始化，防止多次调用污染
    // 虽然在这个生成器逻辑里多次调用其实无所谓，因为是从小推到大覆盖
    // 但为了严谨，我们针对每次查询重置基础值
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    if (n <= 3) return dp[n];

    for (int i = 4; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }
    return dp[n];
}

// ==========================================
// Part 2: 数据构造逻辑 (生成 .in)
// ==========================================

// 生成 [min, max] 范围内的随机整数
int randInt(int min, int max) {
    return rand() % (max - min + 1) + min;
}

void makeData(int fileId) {
    // 构造文件名
    string inName = to_string(fileId) + ".in";
    string outName = to_string(fileId) + ".out";
    
    ofstream fin(inName);
    ofstream fout(outName);
    
    int N;
    
    // 根据测试点编号设计 N 的值，确保覆盖各种情况
    switch(fileId) {
        case 1:
            N = 1; // 最小边界
            break;
        case 2:
            N = 2; // 基础情况
            break;
        case 3:
            N = 3; // 基础情况 (递推公式的前一项)
            break;
        case 4:
            N = 4; // 第一次触发递推公式
            break;
        case 5:
            N = 10; // 小规模数据
            break;
        case 6:
            N = randInt(20, 30); // 中等规模随机
            break;
        case 7:
            N = 36; // 临界点：int (2^31-1) 约为 2.1e9。f(36) 接近 int 极限，f(37) 溢出
            break;
        case 8:
            N = 45; // 必爆 int 范围，检验 long long
            break;
        case 9:
            N = 59; // 接近最大值
            break;
        case 10:
            N = 60; // 题目要求的最大值
            break;
        default:
            N = randInt(1, 60);
            break;
    }
    
    // 1. 写入输入文件 (.in)
    fin << N << endl;
    
    // 2. 计算答案并写入输出文件 (.out)
    fout << solve(N) << endl;
    
    // 关闭文件
    fin.close();
    fout.close();
    
    cout << "Generated Case " << fileId << ": N = " << N << endl;
}

int main() {
    // 初始化随机种子
    srand((unsigned)time(NULL));
    
    cout << "Start generating data..." << endl;
    
    // 循环生成 10 个测试点
    for(int i = 1; i <= 10; i++) {
        makeData(i);
    }
    
    cout << "All done! Please check the .in and .out files." << endl;
    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。

为什么这样设计数据？

• Case 1-3：如果选手直接用循环 for(int i=4...) 且没有处理 N < 4 的情况（比如 if 判断或者预初始化数组），在这几个点可能会输出错误值或乱码。
• Case 7-8：这是一个陷阱区间。dp[35] 约为 11亿，dp[36] 约为 20亿，dp[37] 约为 38亿。int 的最大值是 21亿左右。如果选手用 int，Case 7 可能勉强过（或者刚好挂），但 Case 8 一定会变成负数。这是为了筛查出没有使用 long long 的代码。
• Case 10：最大值 $N=60$，结果约为 $5 \times 10^{16}$，验证算法在大数下的正确性和效率。

这是一个符合 NOIP C++14 竞赛标准的题解代码。

核心思路

1. 状态定义：设 dp[i] 为走到第 i 级台阶的方案总数。
2. 递推公式：因为一步可以走 1、2 或 3 个台阶，所以走到第 i 级只能从第 i-1、i-2 或 i-3 级走过来。
   • 公式：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
3. 初始状态：
   • dp[1] = 1
   • dp[2] = 2
   • dp[3] = 4
4. 数据类型：这是本题最大的坑。$N=60$ 时，方案数会达到 $10^{16}$ 数量级，超过了 int (约 $2\times10^9$) 的范围，必须使用 long long。

标准代码 (C++14)

/**
 * 题目：P10250 [GESP样题 六级] 下楼梯
 * 考点：递推 (动态规划入门)、数据类型选择
 * 难度：普及- / GESP六级
 */

#include <iostream>
#include <vector>

using namespace std;

// 关键点1：数组大小
// 题目要求 N <= 60，开 65 或 70 比较保险，防止越界。
// 建议定义在全局，自动初始化为 0（虽然本题会覆盖赋值，但这是好习惯）
long long dp[70];

void solve() {
    int n;
    cin >> n;

    // 关键点2：边界条件初始化 (Base Case)
    // 1阶：{1} -> 1种
    // 2阶：{1,1}, {2} -> 2种
    // 3阶：{1,1,1}, {1,2}, {2,1}, {3} -> 4种
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    // 关键点3：递推计算
    // 从第 4 阶开始算，直到第 n 阶
    // 如果输入 n < 4 (例如 n=2)，这个循环不会执行，直接输出预设好的 dp[n]，逻辑也是对的
    for (int i = 4; i <= n; i++) {
        // 核心方程：f(i) = f(i-1) + f(i-2) + f(i-3)
        // 注意：这里三个 long long 相加，结果在 long long 范围内，不会溢出
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }

    // 关键点4：输出类型
    // dp数组是 long long，输出自然也是 long long
    cout << dp[n] << endl;
}

int main() {
    // 竞赛标准 IO 优化，加快输入输出速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

代码易错点详细解析

1. long long vs int：

   • 很多同学习惯写 int dp[70];。在 $N$ 比较小（比如 $N \le 30$）时能过，但 $N=60$ 时会发生整型溢出，变成负数或错误的乱码。
   • 经验法则：只要看到递推、累加、阶乘类的题目，且 $N$ 稍大（$>40$），优先考虑 long long。

2. 数组越界：

   • 如果只开了 dp[60]，访问 dp[60] 是合法的（下标 0-59？不对，声明 int a[N] 下标是 0 到 N-1）。
   • 修正：C++中 int a[60] 的有效下标是 0 到 59。如果要存 dp[60]，必须至少开 dp[61]。建议开大一点，如 dp[70]。

3. 循环起点：

   • 循环必须从 4 开始。如果从 3 开始，计算 dp[3] 时会用到 dp[0]（未定义或为0），导致 dp[3] 计算错误（变成 1+2+0=3，实际应为 4）。一定要先手动填好前 3 个坑。

你好！我是你的OI教练。很高兴看到你练习这道《下楼梯》的题目。这是一道非常经典的**递推（动态规划入门）**题目，是用来建立“状态转移”思维的最佳练手题。

虽然它看起来和斐波那契数列（兔子繁殖）很像，但多了一个维度，变成了“三项递推”。

我们照旧，先拿出草稿纸，不要急着写代码，先画图找规律。

1. 读题关键词：你的“雷达”响了吗？

读题时，这几个关键词决定了你的代码能不能拿满分：

1. “1个、2个或3个台阶”：
   • 这告诉我们到达某一级台阶的来源。
   • 如果你站在第 $i$ 级台阶上，你只可能从第 $i-1$ 级、第 $i-2$ 级、或者第 $i-3$ 级走下来。
2. “一共 $N$ 个台阶”：
   • 这是我们的目标状态。
3. “$1 \le N \le 60$”：
   • 红色警报：经典的斐波那契数列第 46 项就会超过 int 的范围（约 21 亿）。
   • 这就好比让你装水，普通的 int 杯子只能装 20 亿滴水。
   • 但这道题是三项相加，增长速度比斐波那契更快！$N=60$ 时的结果是个天文数字（约为 $10^{16}$ 数量级）。
   • 结论：必须使用 long long，否则 60 分变 0 分。

2. 预备知识点

• 递推/递归思想：大事化小，将第 $N$ 级的问题转化为前面几级的问题。
• 一维数组：用于记录每一步的结果，避免重复计算（记忆化）。
• 数据类型范围：深刻理解 int 和 long long 的区别。

3. 启发式教学：草稿纸上的推演

来，我们在草稿纸上模拟小明下楼梯的过程。设 $f(n)$ 为 $n$ 个台阶的方案数。

基础情况（Base Case）：

• $N=1$：只能走 1 步。
  • 方案：{1}
  • $f(1) = 1$
• $N=2$：可以一次走 2 步，也可以分两次走 1 步。
  • 方案：{1,1}, {2}
  • $f(2) = 2$
• $N=3$：
  • 一步步走：{1,1,1}
  • 先1后2：{1,2}
  • 先2后1：{2,1}
  • 一次走完：{3}
  • $f(3) = 4$

推导通项（Induction）： 假设我们要走到第 4 级台阶 ($N=4$)，最后一步是怎么走的？

• 情况A：最后一步走了 1 个台阶。
  • 说明之前已经在第 3 级。有多少种方法到第 3 级？答案是 $f(3)$。
• 情况B：最后一步走了 2 个台阶。
  • 说明之前已经在第 2 级。有多少种方法到第 2 级？答案是 $f(2)$。
• 情况C：最后一步走了 3 个台阶。
  • 说明之前已经在第 1 级。有多少种方法到第 1 级？答案是 $f(1)$。

逻辑闭环： 到第 4 级的方案数 = 到第3级的方案 + 到第2级的方案 + 到第1级的方案

(这和样例输出 #1 吻合！)

总结公式： 对于任意 $i > 3$：

4. 思路提示与代码框架

不要用递归（Recursion），因为 $N=60$ 时递归会重复计算导致超时（除非用记忆化搜索）。建议使用递推（循环）。

步骤：

1. 定义数组：long long dp[65]; （开大一点点，防越界）。
2. 初始化：
   • dp[1] = 1;
   • dp[2] = 2;
   • dp[3] = 4;
3. 循环计算：
   • 从 i = 4 开始，一直循环到 N。
   • 套用公式：dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
4. 输出：dp[N]。

特殊的边界陷阱：

• 如果输入 $N=1, 2, 3$，你的循环条件 i=4 可能进不去。
• 但这没关系，因为我们已经预先填好了 dp[1], dp[2], dp[3]，直接输出 dp[N] 也是对的。

现在，请尝试在你的 IDE 中写出代码。记得一定要用 long long 哦！