题面
题目描述
火车从始发站（称为第 $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 提高组 第一题
题解
本题是一道斐波那契数列背景的模拟题，数据量不大，因此考虑模拟方法解决。
首先模拟本题样例数据的情况。由于第$ 2 $站上、下车人数未知，我们设第二站上、下车人数为$ y $人。
由题意，列出下表。
| 第$ n $站 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
| 从该站开出时的人数 | $a$ | $a$ | $2a$ | $2a+y$ | $3a+2y$ | $4a+4y$ | $m$人全部下车 |
| 总上车数 | $a$ | $y$ | $a+y$ | $a+2y$ | $2a+3y$ | $3a+5y$ | $NaN$ |
| 总下车数 | $0$ | $y$ | $y$ | $a+y$ | $a+2y$ | $2a+3y$ | $NaN$ |
即：$从第(n+1)站开出时的人数=从第n站开出时的人数+总上车数-总下车数(n \in N^*)$
根据上表模拟可知，$m=4a+4y=32$，其中$a=5$，解得$y=3$。
因此，$第4站开出的人数=2a+y=2×5+3=13$。与输出样例#1吻合。
综上，我们可以用模拟的方式递推出所有$a、y$的系数，再通过解出$y$，进而得出答案。
下见代码：
#include<cstdio>
int a,n,m,x,y,tot_ax,tot_yx;
int tot_a[3],tot_y[3]; //从第n站开出时的人数（a、y的系数）
int up_a[3],up_y[3]; //总上车数（a、y的系数）
int down_a[3],down_y[3]; //总下车数（a、y的系数）
int main()
{
scanf("%d%d%d%d",&a,&n,&m,&x);
//初始化
tot_ax=1;
tot_a[0]=1,up_a[0]=1;
tot_a[1]=1,up_y[1]=1,down_y[1]=1;
for(int i=3;i<n;i++)
{
//递推
up_a[2]=up_a[1]+up_a[0];
up_y[2]=up_y[1]+up_y[0];
down_a[2]=up_a[1];
down_y[2]=up_y[1];
tot_a[2]=tot_a[1]+up_a[2]-down_a[2];
tot_y[2]=tot_y[1]+up_y[2]-down_y[2];
//更新递推条件
up_a[0]=up_a[1],up_a[1]=up_a[2];
up_y[0]=up_y[1],up_y[1]=up_y[2];
down_a[0]=down_a[1],down_a[1]=down_a[2];
down_y[0]=down_y[1],down_y[1]=down_y[2];
tot_a[0]=tot_a[1],tot_a[1]=tot_a[2];
tot_y[0]=tot_y[1],tot_y[1]=tot_y[2];
//存储所求的第x站人数的a、y系数
if(i==x) tot_ax=tot_a[2],tot_yx=tot_y[2];
}
if(n>3) y=(m-tot_a[2]*a)/tot_y[2]; //解方程得出y的值
printf("%d",a*tot_ax+y*tot_yx);
return 0;
}补充：为什么初始化时$tot\_ax=1$，解$y$值时时要加入$if(n>3)$的判断？
答：是为了特判$n=1,2$时的特殊情况。否则你会得到一个跑出WA甚至RE的80分程序。
当然，该题解的代码并不够简洁，是因为加入了一些与计算结果无关的模拟过程。
如果要改简洁一点嘛……下次一定！