admin 管理员组文章数量: 887031
车站
题目描述
Description
火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有N个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。试问x站开出时车上的人数是多少？
输入输出格式 Input/output
输入格式：
a(<=20)，n(<=20)，m(<=2000)，和x(<=20)，
输出格式：
从x站开出时车上的人数。
输入输出样例 Sample input/output
样例测试点#1 输入样例：
5 7 32 4
输出样例：
13
解题思路
这个题是模拟掺杂斐波那契数列。
现在用b【i】表示第i站的上车人数，c【i】表示第i站的下车人数，sum【i】表示在第i站上下车后车上的总人数。设在第二站上车的人数为k
下面通过列举b【i】看能不能发现点什么~
- b【1】：=a
- b【2】：=k
- b【3】：=a+k
- b【4】：=a+2k
- b【5】：=2a+3k
- b【6】：=3a+5k
通过比较每一个b【i】的系数，可发现，从第3站开始，a和k的系数都和斐波那契数列有关系，即可以递推出b【i】。现在用fa【i】表示b【i】中a的系数，用fb【i】表示b【i】中k的系数。
b【1】：=a；c【1】：=0；b【2】：=k；c【2】：=k；
可得sum【i】:=b【1】-c【1】+b【2】-c【2】+b【3】-c【3】+b【4】-c【4】+……+b【i-1】-c【i-1】+b【i】-c【i】
= a-0+b【2】-k
+b【3】-c【3】
+b【4】-c【4】
+……
+b【i-1】-c【i-1】
+b【 i 】-c【 i 】
题目中“下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站）”，可知b【i】=c【i+1】。从而消除其中的一些项。
得：
sum【i】：=a-k+b【i】
而sum【n-1】：=a-k+b【n-1】=a-k+fa【n-1】* a+fb【n-1】 * k=m，
从而可以求出k：=(m-a-a*fa[n-1]) div (fb[n-1]-1)
那么答案sum【x】可求。
代码
var k,ans,i,a,n,m,x:longint;fa,fb:array[1..100000]of longint;
beginreadln(a,n,m,x);fa[1]:=1;fa[2]:=0;fa[3]:=1;fa[4]:=1;fb[1]:=0;fb[2]:=1;fb[3]:=1;fb[4]:=2;if n>=5 thenfor i:=5 to n dobeginfa[i]:=fa[i-1]+fa[i-2];fb[i]:=fb[i-1]+fb[i-2];end;k:=(m-a-a*fa[n-1])div(fb[n-1]-1);write(a-k+fa[x]*a+fb[x]*k);
end.评测结果 Result
测试点 #1：通过该测试点。 得分25，耗时0ms，内存3112kB。
测试点 #2：通过该测试点。 得分25，耗时0ms，内存3117kB。
测试点 #3：通过该测试点。 得分25，耗时0ms，内存3088kB。
测试点 #4：通过该测试点。 得分25，耗时0ms，内存3088kB。本文标签： 车站
版权声明：本文标题：车站 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687870025h151467.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论