題目描述

火車從始發站（稱為第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

話說這道題真心挺惡心，現推的時候還是挺麻煩的。。。來吧，看下面表格。。。在這個地方我們規定在第二站上車的人數為t。f[]為斐波那契數列前幾項。站點標號 上車人數 下車人數 車上人數 變化人數1 a 0 a a2 t a a 03 a+t t 2a a4 a+2t a+t 2a+t t5 2a+3t a+2t 3a+2t a+t6 3a+5t 2a+3t 4a+4t a+2t7 5a+8t 3a+5t 6a+7t 2a+3t8 0 6a+7t 0 4a+4t通過看上面的表格有沒有發現一個規律？？在站點上車人數滿足f[n-2]*a+f[n-1]*t;通過觀察整個過程，你還會哦發現這樣一個關系：最后一站的人數m+第二站上車的人數等于倒數第二站上車的人數+第一站的人數。即：m+t=f[n-1-2]*a+f[n-1-1]*t+a;通過這個關系我們可以很快的求出t的值，這樣在第x站上車的人數等于：f[x-2]*a+f[x-1]*t;在車上的人數等于：（f[x-2]）*a+（f[x-1]+1）*t

　　

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=10001; int a,n,m,x,t,f[N]; inline void read(int &n) {char c='+';int x=0;bool flag=0;while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48,c=getchar();}flag==1?n=-x:n=x; } int main() {read(a);read(n);read(m);read(x);f[1]=1;f[2]=1;for(int i=3;i<=n;i++)f[i]=f[i-1]+f[i-2];t=(m-(f[n-3]+1)*a)/(f[n-2]-1);printf("%d",(f[x-2]+1)*a+(f[x-1]-1)*t);return 0; }

　　

總結

以上是生活随笔為你收集整理的P1011 车站的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。