洛谷笔记 - P1011 [NOIP1998 提高组] 车站

发表于 更新于 本文字数： 491 阅读时长 ≈ 2 分钟

暴力出奇迹…… 算是？

题目描述

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

输入格式

输入只有一行四个整数，分别表示始发站上车人数 aa，车站数 nn，终点站下车人数 mm 和所求的站点编号 xx。

输出格式

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

样例 #1

样例输入 #1

1
5 7 32 4

样例输出 #1

1
13

提示

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

代码

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
//P1011 [NOIP1998 提高组] 车站
//https://www.luogu.com.cn/problem/P1011

//Tag: 数学,斐波那契,Fibonacci,NOIp 提高组,1998
//https://www.luogu.com.cn/record/84497451

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int a,n,m,x;
    cin>>a>>n>>m>>x;
    if(x<=2){
        cout<<a<<endl;
        return 0;
    }
    if(x==n){
        cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<=m;i++){ //因为没说第二辆车上、下了几个人，遂递归
        int sc[21]={a,i},car[21]={a,a};
        for(int i=2;i<n-1;i++){
            car[i]=car[i-1]+sc[i-1]+sc[i-2];
            car[i]-=sc[i-1];
            sc[i]=sc[i-1]+sc[i-2];
        }
        if(car[n-2]==m){
            cout<<car[x-1]<<endl;
            return 0;
        }
    }
    return 0;
}

参考资料

题解 P1011 【车站】