「LGOJ」车站

题意

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

Link

题解

​ 第一眼考虑可以找规律推公式的

​ 我们不妨设a为本来是人数,b为增加的人数

站台数N 1 2 3 4 5 6
上客数 a b a+b a+2b 2a+3b 3a+5b
下客数 0 b b a+b a+2b 2a+3b
总数 a a 2a 2a+b 3a+2b 4a+4b

设a系数为p_{i},b系数为q_{i}

则有
$$
P_{i}=p_{i-1}+p_{i-2}-1
$$

$$
q_{i}=q_{i-1}+q_{i-2}+1
$$

注意前两项都为无规律,初始化注意啦

然后根据m列方程解出来即可 ,有:
$$
b = ( m - p[n-1] * a ) / q[n-1];
$$

$$
ans = p[x] * b + q[x] * y;
$$

答案就出来啦qwq

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

#define ll long long
#define RE register

int a,n,m,x,y,ans,p[30],q[30];

inline void fread(int &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}

int main(){
fread(a);
fread(n);
fread(m);
fread(x);
p[1] = 1;
p[2] = 1;
p[3] = 2;
for(RE int i = 4; i < n;i++) {
p[i] = p[i-1] + p[i-2] - 1;
q[i] = q[i-1] + q[i-2] + 1;
}
y = ( m - p[n-1] * a ) / q[n-1];
ans = p[x] * a + q[x] * y;
std::printf("%d",ans);
return 0;
}

0%