朝田诗乃 的博客

朝田诗乃 的博客

题解 P1011 【车站】

posted on 2016-09-22 18:26:15 | under 题解 |

设第二站上车b人,f[i]为每站上车人数

依题意得

f[1]=a f[2]=b f[3]=1b+a f[4]=2b+a f[5]=3b+2a f[6]=5b+3a ……

可以发现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);
}