[题解]P1011 [NOIP1998 提高组] 车站

题目难点

对数学功底的考察，能否根据题目描述建立起数学公式, 解出关键的未知数(第二次上下车的人数)

题目

洛谷链接： [P1011 NOIP1998 提高组] 车站 - 洛谷 | 计算机科学教育新生态

[NOIP1998 提高组] 车站

题目描述

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

输入格式

输入只有一行四个整数，分别表示始发站上车人数 $a$，车站数 $n$，终点站下车人数 $m$ 和所求的站点编号 $x$。

输出格式

输出一行一个整数表示答案：从 $x$ 站开出时车上的人数。

样例 #1

样例输入 #1

1
>5 7 32 4

样例输出 #1

1
>13

提示

对于全部的测试点，保证 $1 \leq a \leq 20$，$1 \leq x \leq n \leq 20$，$1 \leq m \leq 2 \times 10^4$。

NOIP1998 提高组 第一题

题解

对于这道题而言，我们发现存在两个斐波拉契数列，一个是下车，一个是上车

我们不妨设置第二站上下车的人数为b，

显然，getOn[1] = a, getOff[1] = 0, getOn[2] = getOff[2] = b.

对于第n站上车的人数而言(n>2)：

getOn[n] = getOn[n-2]+getOn[n-1]

对于第n站下车的人数而言(n>2):

getOff[n] = getOn[n-1]

问题是，我们并不知晓b为何值，b成为了解决这个车站问题的关键节点。

突破点是我们接受到的m,即第n站下车的总人数，实际上即车驶离第n-1站时车上的人数。

显然m 为所有 getOn[i] - getOff[i] 之和 (i<=n-1)

通过表格

1 2 3 4 … k
getOn a b a+b a+2b … getOn[k]
getOff 0 b b a+b … getOn[k-1]

我们不妨发现，getOff[i]与getOn[i-1]抵消，

于是乎，在已知b的值的情况下，我们得到：

m = a-b + getOn[n-1]

我们已经知道a和m,为了得到b,我们还需要getOn[n-1],

在我们不知道b时，我们可以把getOn[n-1]分解成

getOn[n-1] = fibcal(a,0,n-1) + fibcal(0,1,n-1) * b

其中, fibcal为计算斐波拉契数的函数

将此式子带入上式，我们可以求出b的值,

同理，之后对于所求的车开出第x站时的车上人数res为:

res = a-b+fibcal(a,b,x)

代码如下:

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
41
42
43
#include<iostream>

using namespace std;

int main()
{
    long fibcal(int,int, int);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,x;
    int a;
    long res;
    cin >> a >> n >> m >> x;
    int part1 = fibcal(0,1,n-1);
    int part2 = fibcal(a,0,n-1);
    int b = (n==2? m-a :(m-a-part2)/(part1-1));
    if(x > 3){
        res = a-b+fibcal(a,b,x);
        cout << res << endl;
    }
    else if(x==1){
       cout << a << endl;
    }
    else if(x==2){
        cout << b << endl;
    }
}

long fibcal(int a, int b, int n){
    if(n == 1) return a;
    if(n == 2) return b;
    long res[3];
    int i;
    res[0] = a;
    res[1] = b;
    for(i=0; i<n-2; i++){
        res[(i+2)%3] = res[i%3] + res[(i+1)%3];
    }
    i--;
    i = (i+2) % 3;
    return res[i];
}