LuoguP1011车站题解

题目描述

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

输入输出格式

输入格式:
a(<=20),n(<=20),m(<=2000),和x(<=20),
输出格式:
从x站开出时车上的人数。

输入输出样例

输入样例#1:

5 7 32 4
输出样例#1:

13

这篇用来测试代码高亮咯!第一篇题解祭.
题解:
设第二站上车b人,f[i]为每站上车人数
依题意得
[codee]
f[1]=a
f[2]=b
f[3]=1b+a
f[4]=2b+a
f[5]=3b+2a
f[6]=5b+3a
……
[/codee]
可以发现a,b系数为斐波那契数列 设fibo[]为斐波那契数列
fibo[]={1,1,2,3,5,8,13,21,34……}
则第i站上车人数(i>2)为
f[i]=fibo[i-1]*b+fibo[i-2]*a;
∵下车人数=上一站上车人数
∴中间的上下车不必模拟,没有意义,可以忽略
再者,终点站没有人上车
不难得出
m=f[n-1]+a-b
上一站上车+起始站人数-第二站上车的人数=最后下车的人数
然后求出b就好啦!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int main()
{
    int a,b,n,m,x,fibo[21]={0};
    scanf("%d%d%d%d",&a,&n,&m,&x);
    fibo[0]=0;fibo[1]=1;
    for(int i=2;i<=n;i++)
        fibo[i]=fibo[i-1]+fibo[i-2];
    //f[n-1]=fibo[n-2]*b+fibo[n-3]*a
    //m=fibo[n-2]*b+fibo[n-3]*a+a-b
    //m=(fibo[n-2]-1)*b+(fibo[n-3]+1)*a
    b=(m-(fibo[n-3]+1)*a)/(fibo[n-2]-1);
    printf("%d",(fibo[x-1]-1)*b+(fibo[x-2]+1)*a);
}

 

点赞
  1. 凌峰说道:

    不错啊~

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00