题解 P1011 【车站】

· · 题解

其实这道题根本就没有你们想象的那么复杂。

思路

此题标签：斐波那契数列。就往这个方面想就好了，只是要找找规律。

规律

设第二站上下车人数为b。

经过几步计算，可以得到下表：

显然前两行都与前面的数有关，就猜测第三行也与前面的数有关，于是得到第四行。很明显可以发现第四行a的系数比第三行多1，b的系数比第三行少1。

所以不用管前两行，把第三行直接列出来就行了。方程：

//sum1表示a的系数，sum2表示b的系数
sum1[i]=sum1[i-1]+sum1[i-2]-1;//前两个的和-1
sum2[i]=sum2[i-1]+sum2[i-2]+1;//前两个的和+1

后续

算完这些，b也就能够根据a和m求出来了。很显然，a*sum1[n-1]+b*sum2[n-1]=m。即b=(m-a*sum1[n-1])/sum2[n-1]。

于是答案就是a*sum1[x]+b*sum2[x]。

代码

其实上面几乎已经把代码贴出来了，但我相信绝大部分人会看到这里。

代码时间：3ms（挺快），长度：15行（分析都不止15行诶）

#include<cstdio>
using namespace std;
int sum1[25],sum2[25];//a和b的系数
int main(){
    int a,n,m,x;
    scanf("%d%d%d%d",&a,&n,&m,&x);
    sum1[2]=1,sum1[3]=2;//初始化
    for(int i=4;i<n;i++){//遍历（必须从4开始，前面没有规律）
        sum1[i]=sum1[i-1]+sum1[i-2]-1;//计算系数，见上
        sum2[i]=sum2[i-1]+sum2[i-2]+1;
    }
    int b=(m-a*sum1[n-1])/sum2[n-1];//公式
    printf("%d",a*sum1[x]+b*sum2[x]);
    return 0;//华丽结束
}

尽管代码很短，但写一篇题解也不容易，所以别忘了点个赞！