【NOIP】1998真题解析 luogu-P1011 车站 | GESP四、五级以上可练习

NOIP 1998 提高组真题，主要考察递推与斐波那契数列规律应用。题目需要对上下车人数的状态进行合理地抽象模拟并求解未知变量。GESP四、五级以上可练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。

luogu-P1011 [NOIP 1998 提高组] 车站

题目要求

题目描述

火车从始发站（称为第 $1$ 站）开出，在始发站上车的人数为 $a$，然后到达第 $2$ 站，在第 $2$ 站有人上、下车，但上、下车的人数相同，因此在第 $2$ 站开出时（即在到达第 $3$ 站之前）车上的人数保持为 $a$ 人。从第 $3$ 站起（包括第 $3$ 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 $n-1$ 站），都满足此规律。现给出的条件是：共有 $n$ 个车站，始发站上车的人数为 $a$，最后一站下车的人数是 $m$（全部下车）。试问 $x$ 站开出时车上的人数是多少？

输入格式

输入只有一行四个整数，分别表示始发站上车人数 $a$，车站数 $n$，终点站下车人数 $m$ 和所求的站点编号 $x$。

输出格式

输出一行一个整数表示答案：从 $x$ 站开出时车上的人数。

输入输出样例 #1

输入 #1

5 7 32 4

输出 #1

13

说明/提示

【数据范围】

对于全部的测试点，保证 $1 \leq a \leq 20$，$1 \leq x \leq n \leq 20$，$1 \leq m \leq 2 \times 10^4$。

NOIP1998 提高组 第一题

---

题目分析

这道题是一道经典的递推（或模拟）与数学规律相结合的题目。题目要求根据列车各站上下车人数的规则，推导并在已知终点前一站（第 $n-1$ 站）开出时总人数为 $m$ 的情况下，求出第 $x$ 站开出时的人数。由于第二站上车与下车的人数未知（设为 $k$），但整个过程的所有人数变化都可以用 $a$ 和 $k$ 的一次分量（或者说系数）来分离表示。

我们可以通过两种方式来解这道题：

1. 系数递推法（模拟法）

我们可以把每一站的上车人数、下车人数以及车上总人数，全都利用多项式表示成 $C_1 \times a + C_2 \times k$ 的形式（其中 $C_1, C_2$ 是推导出来的常数系数）。由此我们可以建立两套并行的递推过程，分别记录状态中 $a$ 的系数和 $k$ 的系数变化：

• 初始化：
  • 第 1 站：上车 $a$（$a$ 的系数为 1，$k$ 为 0），下车 0，开出时总人数为 $a$。
  • 第 2 站：上车 $k$（$a$ 的系数为 0，$k$ 为 1），下车 $k$（$a$ 的系数为 0，$k$ 为 1），开出时总人数依然为 $a$（$a$ 系数为 1，$k$ 为 0）。
• 递推过程（从第 3 站到第 $n-1$ 站）： 根据题意，“上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数”，所以有：
  • 第 $i$ 站上车人数 = 第 $i-1$ 站上车人数 + 第 $i-2$ 站上车人数； （代码对应部分：upOne[i] = upOne[i - 1] + upOne[i - 2];）
  • 第 $i$ 站下车人数 = 第 $i-1$ 站上车人数； （代码对应部分：downOne[i] = upOne[i - 1];）
  • 第 $i$ 站开出时总人数 = 第 $i-1$ 站开出时总人数 + 第 $i$ 站上车人数 - 第 $i$ 站下车人数。 （代码对应部分：totalOne[i] = totalOne[i - 1] + upOne[i] - downOne[i]; 同理可算出对未知数 $k$ 的系数） 最后在终点的上一站，即第 $n-1$ 站开出时，我们就得到了一个关于未知数 $k$ 的一元一次方程：$totalOne[n-1] \times a + totalTwo[n-1] \times k = m$。 从中解出 $k$ 的值（代码中即为 k = (m - totalOne[n - 1] * a) / totalTwo[n - 1];），再代入第 $x$ 站推导出的系数公式中求值，即可得到最终答案。

2. 斐波那契数列找规律法

通过手动推导前几站的上下车人数及总人数，我们可以发现，各项系数的生成与斐波那契数列（Fibonacci sequence）密切相关。

• 设斐波那契数列为 $F_1 = 1,\ F_2 = 1,\ F_3 = 2,\ F_4 = 3 \dots$
• 规律分析：从第 3 站开始（前两站固定等于 $a$），第 $i$ 站开出时的总人数可以表达为： $(F_{i-2} + 1) \times a + (F_{i-1} - 1) \times k$。 在代码中则对应为 (fab[i - 2] + 1) * a + (fab[i - 1] - 1) * k。
• 根据终端站下车情况：第 $n$ 站所有人全部下车且人数为 $m$，这说明第 $n-1$ 站开出时的总人数恰好等于 $m$。
• 代入公式得到：$(F_{(n-1)-2} + 1) \times a + (F_{(n-1)-1} - 1) \times k = m$，即 $(F_{n-3} + 1) \times a + (F_{n-2} - 1) \times k = m$。 通过移项并做除法可解得 $k$ 的确切值（在示例代码中被命名为 a2，其对应代码为 int a2 = (m - (fab[n - 3] + 1) * a) / (fab[n - 2] - 1);）。
• 求出 $k$ 后，将 $k$ 代入第 $x$ 站对应的求值公式即可直接输出结果。

两种方法核心思路一致，都巧妙避开了直接求解未知的第二站上车人数的麻烦，而是分别应用了维护记录未知数的系数模拟与直接从数列中归纳数学规律求解的思路。

---

示例代码

解法一：系数递推法（模拟过程）

#include <iostream>

// upOne, downOne, totalOne 分别用来记录每一站(上车、下车、开出时车上)
// 第一站上车人数 a 的系数
int upOne[25];     // 上车人数中 a 的系数
int downOne[25];   // 下车人数中 a 的系数
int totalOne[25];  // 车上总人数中 a 的系数

// upTwo, downTwo, totalTwo 分别用来记录每一站(上车、下车、开出时车上)
// 第二站上车未知人数 k 的系数
int upTwo[25];     // 上车人数中 k 的系数
int downTwo[25];   // 下车人数中 k 的系数
int totalTwo[25];  // 车上总人数中 k 的系数

int main() {
    int a, n, m, x;
    std::cin >> a >> n >> m >>
        x;  // a: 第一站上车人数, n: 车站总数, m: 终点站下车总人数, x:
            // 要求求出的第x站开出时的人数

    // 初始化第 1 站的情况：
    // 第 1 站上车 a 人 (此时 a 的系数为 1, k 的系数为 0)
    upOne[1] = 1;
    downOne[1] = 0;
    totalOne[1] = 1;  // 开出时车上只有 a 人

    upTwo[1] = 0;
    downTwo[1] = 0;
    totalTwo[1] = 0;

    // 初始化第 2 站的情况：
    // 第 2 站上车人数为 k，下车人数也为 k
    // 因此上车人数中 a 的系数为 0，下车中 a 的系数为
    // 0。总体车上依然等于第一站留下来的 a
    upOne[2] = 0;
    downOne[2] = 0;
    totalOne[2] = 1;

    // 第 2 站上车 k 人，所以 k 的系数为 1；题意说下车人数等于上车人数，因此下车
    // k 的系数也为 1 车上 k 增加 1，又减少 1，所以开出时车上 k 的系数依然是 0
    upTwo[2] = 1;
    downTwo[2] = 1;
    totalTwo[2] = 0;

    // 从第 3 站开始按照题意规则进行递推，直到第 n-1 站
    for (int i = 3; i <= n - 1; i++) {
        // 第一站上车人数“a”部分的系数变化：
        upOne[i] =
            upOne[i - 1] + upOne[i - 2];  // 这一站上车数 = 前两站上车数之和
        downOne[i] = upOne[i - 1];        // 这一站下车数 = 前一站上车数
        totalOne[i] = totalOne[i - 1] + upOne[i] -
                      downOne[i];  // 车上总人数 = 原来的人 + 上车 - 下车

        // 第二站上车未知人数“k”部分的系数变化：
        upTwo[i] = upTwo[i - 1] + upTwo[i - 2];
        downTwo[i] = upTwo[i - 1];
        totalTwo[i] = totalTwo[i - 1] + upTwo[i] - downTwo[i];
    }

    int k;
    // 题目给出第 n 站(终点站)的人全部下车，总人数为 m
    // 这说明第 n-1 站开出时的总人数恰好等于 m
    // 即：totalOne[n-1] * a + totalTwo[n-1] * k = m
    // 判断除数 totalTwo[n - 1] 不为 0，防止运行错误（例如当 n=2 或 n=3
    // 时此除数为 0）
    if (n > 1 && totalTwo[n - 1] != 0) {
        k = (m - totalOne[n - 1] * a) / totalTwo[n - 1];
    } else {
        k = 0;  // 如果除数为 0（本题没这数据），给 k 一个默认值
    }

    // 套用算出的 k，根据第 x 站对应存储的 a 和 k 的系数，计算并输出第 x
    // 站开出时的人数
    int ans = totalOne[x] * a + totalTwo[x] * k;
    std::cout << ans << std::endl;
    return 0;
}

解法二：斐波那契数列数学规律法

#include <iostream>

// fab 数组用来存储斐波那契数列，用于推导每一站 a 和 k 的系数规律
int fab[25];
int main() {
    int a, n, m, x;
    std::cin >> a >> n >> m >>
        x;  // a: 第一站上车人数, n: 车站总数, m: 终点站下车总人数, x:
            // 要求求出的第x站开出时的人数

    // 初始化斐波那契数列的前两项
    fab[1] = 1;
    fab[2] = 1;
    // 计算并生成斐波那契数列 (用于表示系数规律)
    for (int i = 3; i <= n; i++) {
        fab[i] = fab[i - 1] + fab[i - 2];
    }

    // 根据从第3站开始的车上总人数的规律得出：
    // 第 i 站开出时车上的总人数中：起点站 a 的系数等于 fab[i - 2] +
    // 1；第二站未知上车人数 k 的系数等于 fab[i - 1] - 1 题目已知第 n
    // 站(终点站)下车人数等于 m，也就是第 n - 1 站开出时的车上总人数为 m
    // 即：(fab[(n - 1) - 2] + 1) * a + (fab[(n - 1) - 1] - 1) * a2 = m
    // 化简得：(fab[n - 3] + 1) * a + (fab[n - 2] - 1) * a2 = m
    // 移项求解 a2 (即第二站的未知上车人数 k)：
    int a2 = (m - (fab[n - 3] + 1) * a) / (fab[n - 2] - 1);

    int ans;
    // 如果求的是前两站开出时的人数，直接等于第一站上车的人数 a
    if (x == 1 || x == 2) {
        ans = a;
    } else {
        // 对于第3站及以后，套用推导出的公式计算第 x 站车上的总人数：
        // ans = (a的系数) * a + (k的系数) * k
        ans = (fab[x - 2] + 1) * a + (fab[x - 1] - 1) * a2;
    }
    std::cout << ans << std::endl;  // 输出第 x 站开出时的人数
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号