火车从始发站（称为第 1 1 1 站）开出，在始发站上车的人数为 a a a，然后到达第 2 2 2 站，在第 2 2 2 站有人上、下车，但上、下车的人数相同，因此在第 2 2 2 站开出时（即在到达第 3 3 3 站之前）车上的人数保持为 a a a 人。从第 3 3 3 站起（包括第 3 3 3 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 ( n − 1 ) (n-1) (n−1) 站），都满足此规律。现给出的条件是：共有 n n n 个车站，始发站上车的人数为 a a a ，最后一站下车的人数是 m m m（全部下车）。试问 x x x 站开出时车上的人数是多少？
输入只有一行四个整数，分别表示始发站上车人数 a a a，车站数 n n n，终点站下车人数 m m m 和所求的站点编号 x x x。
输出一行一个整数表示答案：从 x x x 站开出时车上的人数。
5 7 32 4
13
对于全部的测试点，保证 1 ≤ a ≤ 20 1 \leq a \leq 20 1≤a≤20， 1 ≤ x ≤ n ≤ 20 1 \leq x \leq n \leq 20 1≤x≤n≤20， 1 ≤ m ≤ 2 × 1 0 4 1 \leq m \leq 2 \times 10^4 1≤m≤2×104。
根据题目描述，可以先打表观察题目给出的数据的规律
可以看出，净上车人数从第3站开始满足斐波那契数列规律。但是k是一个未知数，所以要通过解方程的方式来求出k。
假设最后求出从
n
−
1
n-1
n−1站驶离时车上人数为
λ
a
+
ξ
k
\lambda a+\xi k
λa+ξk,则该值等于n站下车人数m。即
λ
a
+
ξ
k
=
m
\lambda a+\xi k=m
λa+ξk=m。
求出在x站驶离时车上人数为
α
a
+
β
k
\alpha a+\beta k
αa+βk,此时将k代入即可。
用结构体 来表示每一站的净上车人数为
x
a
∗
a
+
x
k
∗
k
x_a*a+x_k*k
xa∗a+xk∗k,只需要存储系数即可。
struct sta {
int xa = 0;
int xk = 0;
sta operator+(sta rhs) {
sta re;
re.xa = this->xa + rhs.xa;
re.xk = this->xk + rhs.xk;
return re;
}
};
代码如下
#include<iostream>
#include<vector>
using namespace std;
struct sta {
int xa = 0;
int xk = 0;
sta operator+(sta rhs) {
sta re;
re.xa = this->xa + rhs.xa;
re.xk = this->xk + rhs.xk;
return re;
}
};
int main() {
int a, n, m, x;
cin >> a >> n >> m >> x;
if (x == 1) {
cout << a << endl;
return 0;
}
if (x == 2) {
cout << a << endl;
return 0;
}
if (x == n) {
cout << 0 << endl;
return 0;
}
if (x == 3) {
cout << a * 2 << endl;
return 0;
}
vector<sta> dp(n + 1, {0,0});
dp[1] = { 1,0 };
dp[2] = { 0,0 };
dp[3] = { 1,0 };
dp[4] = { 0,1 };
sta count{ 2,1 };
sta countx{ 2,1 };
for (int i = 5; i <= n-1; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
count = count + dp[i];
if (i <= x)
countx = countx + dp[i];
}
//cout << count.xa << " " << count.xk << endl;
int k = m - count.xa * a;
k /= count.xk;
//cout << "k" << k << endl;
cout << countx.xa * a + countx.xk * k << endl;
}