洛谷 P1011 车站问题：斐波那契递推与打表技巧
本题的核心在于发现人数变化的递推规律。设起始站上车人数为参数 a 和 b，观察各站人数关系：
规律推导
用二元组 (p, q) 表示某量关于 a 和 b 的系数：
| 站点 | 上车系数 | 下车系数 | 净增系数 | 剩余系数 |
|---|---|---|---|---|
| 1 | (1, 0) | (0, 0) | (0, 0) | (1, 0) |
| 2 | (0, 1) | (0, 1) | (0, 0) | (1, 0) |
| 3 | (1, 1) | (0, 1) | (1, 0) | (2, 0) |
| 4 | (1, 2) | (1, 1) | (0, 1) | (2, 1) |
| 5 | (2, 3) | (1, 2) | (1, 1) | (3, 2) |
| 6 | (3, 5) | (2, 3) | (1, 2) | (4, 4) |
关键发现：从第3站开始，上车人数系数满足斐波那契递推：
u[i] = u[i-2] + u[i-1]
且下车人数等于前一站上车人数：d[i] = u[i-1]
打表生成程序
预先计算各站系数，存储为三维数组 coef[站点][类型][参数]：
#include <cstdio>
int coef[25][5][3];
int main() {
freopen("table.txt", "w", stdout);
// 初始化前两站
coef[1][1][1] = 1; // 第1站上车：a
coef[1][4][1] = 1; // 第1站剩余：a
coef[2][1][2] = 1; // 第2站上车：b
coef[2][2][2] = 1; // 第2站下车：b
coef[2][4][1] = 1; // 第2站剩余：a
// 递推计算 3~20 站
for (int i = 3; i <= 20; i++) {
for (int k = 1; k <= 2; k++) { // 分别处理a和b的系数
// 上车 = 前两站上车之和
coef[i][1][k] = coef[i-2][1][k] + coef[i-1][1][k];
// 下车 = 前一站上车
coef[i][2][k] = coef[i-1][1][k];
// 净增 = 上车 - 下车
coef[i][3][k] = coef[i][1][k] - coef[i][2][k];
// 剩余 = 前一站剩余 + 净增
coef[i][4][k] = coef[i-1][4][k] + coef[i][3][k];
}
}
// 输出打表结果
for (int i = 1; i <= 20; i++) {
printf("%d:\n", i);
for (int j = 1; j <= 4; j++) {
printf(" (%d, %d)\n", coef[i][j][1], coef[i][j][2]);
}
}
return 0;
}精简后的提交代码
实际只需保留"剩余人数"的系数，将打表结果硬编码：
#include <iostream>
using namespace std;
// 打表结果：remain[i][k] 表示第i+1站剩余人数中a/b的系数
// 索引从0开始，对应第2~20站
int remain[20][2] = {
{1, 0}, // 第2站
{2, 0}, // 第3站
{2, 1}, // 第4站
{3, 2}, // 第5站
{4, 4}, // 第6站
{6, 7}, // 第7站
{9, 12}, // 第8站
{14, 20}, // 第9站
{22, 33}, // 第10站
{35, 54}, // 第11站
{56, 88}, // 第12站
{90, 143}, // 第13站
{145, 232},// 第14站
{234, 376},// 第15站
{378, 609},// 第16站
{611, 986},// 第17站
{988, 1596},// 第18站
{1598, 2583},// 第19站
{2585, 4180} // 第20站
};
int main() {
int initA, totalStation, finalCnt, queryStation;
cin >> initA >> totalStation >> finalCnt >> queryStation;
// 注意：finalCnt是第totalStation站开出后的人数
// 对应 remain[totalStation-2]
int idx = totalStation - 2;
int coefA = remain[idx][0];
int coefB = remain[idx][1];
// 解出参数b
int initB = (finalCnt - coefA * initA) / coefB;
// 查询第queryStation站开出后人数
int ansIdx = queryStation - 2;
int result = remain[ansIdx][0] * initA + remain[ansIdx][1] * initB;
cout << result << endl;
return 0;
}注意事项
- 数组下标从0开始，站点编号需做偏移转换
- 第1站开出后剩余人数恒为
initA，第2站为initA，故打表从第3站（索引0）开始 - 利用第n站总人数可唯一确定参数b，再回代求任意站人数
