原理

问题目标：确定火车在第x站出站时车上的人数。已知始发站人数a，终点站人数m，以及车站上下车人数的递推规律。

核心算法：

• ​递推关系：每一站的上车人数遵循斐波那契数列规律，下车人数为前一站的上车人数。
• ​系数分离：将上车人数和总人数中的a和b的系数分离，建立方程求解未知数b的值，再代入计算第x站的人数。

步骤

1. ​输入处理：读取a, n, m, x，处理特殊情况（如x为终点站或n=2）。
2. ​计算上下车系数：
   • u_a[k]和u_b[k]分别表示第k站上车人数中a和b的系数，遵循斐波那契递推。
3. ​计算总人数系数：
   • f[k]和g[k]表示第k站总人数中a和b的系数，通过递推式累计变化量。
4. ​求解方程：利用终点站条件（总人数为m）建立方程，解出b的值。
5. ​计算结果：代入b的值，计算第x站的总人数。

图示法表示步骤（示例：a=5, n=7, m=32, x=4）

1. ​计算u_a和u_b：

   u_a = [0,1,0,1,1,2,3]  
   u_b = [0,0,1,1,2,3,5]  

   • 第6站上车人数系数为a=3, b=5。
2. ​计算f和g：

   f = [0,1,1,2,2,3,4]  
   g = [0,0,0,0,1,2,4]  

3. ​解方程：4a +4b =32 → b=3。
4. ​计算第4站人数：2 * 5 +1 * 3 =13。

代码关键行注释

int main() {
    int a, n, m, x;
    cin >> a >> n >> m >> x;

    // 特殊情况处理
    if (x == n) { cout << 0 << endl; return 0; }
    if (n == 2) { cout << a << endl; return 0; }

    // 计算u_a和u_b（上下车系数）
    vector<int> u_a(max_k + 1), u_b(max_k + 1);
    u_a[1] = 1; u_b[1] = 0; // 第1站上车a，无b
    u_a[2] = 0; u_b[2] = 1; // 第2站上车b，无a
    for (int k = 3; k <= max_k; ++k) {
        u_a[k] = u_a[k-2] + u_a[k-1]; // 斐波那契递推
        u_b[k] = u_b[k-2] + u_b[k-1];
    }

    // 计算总人数系数f和g
    vector<int> f(max_k + 1), g(max_k + 1);
    f[1] = 1; g[1] = 0; // 第1站总人数为a
    f[2] = 1; g[2] = 0; // 第2站总人数为a（特殊处理）
    for (int k = 3; k <= max_k; ++k) {
        f[k] = f[k-1] + u_a[k] - u_a[k-1]; // 递推总人数变化量
        g[k] = g[k-1] + u_b[k] - u_b[k-1];
    }

    // 解方程求b
    int fn = f[max_k], gn = g[max_k];
    int b = (m - fn * a) / gn;

    // 计算第x站结果
    cout << f[x] * a + g[x] * b << endl;
}

时间复杂度

• ​时间复杂度：O(n)，递推计算u_a/u_b和f/g数组。
• ​空间复杂度：O(n)，存储中间数组。

总结

1. ​代码特点：
   • 通过分离a和b的系数，将问题转化为线性方程求解。
   • 特殊处理n=2和x为终点站的情况，避免无效计算。
2. ​潜在优化：
   • 可优化空间复杂度，仅保留必要变量而非数组。
3. ​适用场景：
   • 适用于车站数较大的场景，但时间复杂度仍为线性，效率较高。