题解 P1011 【车站】

其实这道题根本就没有你们想象的那么复杂。 ## 思路 此题标签：斐波那契数列。就往这个方面想就好了，只是~~要找找规律~~。 ### 规律 设第二站上下车人数为$b$。 经过几步计算，可以得到下表：  显然前两行都与前面的数有关，就猜测第三行也与前面的数有关，于是得到第四行。很明显可以发现第四行$a$的系数比第三行多$1$，$b$的系数比第三行少$1$。 所以不用管前两行，把第三行直接列出来就行了。方程： ```cpp //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行诶~~） ```cpp #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;//华丽结束 } ``` 尽管代码很短，但写一篇题解也不容易，所以别忘了点个赞！