当前位置:首页 > 递推 > 正文
SSOJ2348火车站(NOIP1998)
161+

题目大意:火车开出时车上有x人,第二个站上车y人、下车y人,之后上下车规律是上车人数是前两站上车之和,下车人数是上一站上车人数,到达低n站时有m人,那么第k站开出时有多少人?

题目描述

火车从始发站(称为第1站)开出,在始发站上车的人数为a,然后到达第2站,在第2站有人上、下车,但上、下车的人数相同,因此在第2站开出时(即在到达第3站之前)车上的人数保持为a人。从第3站起(包括第3站)上、下车的人数有一定的规律:上车的人数都是前两站上车人数之和,而下车人数等于上一站上车人数,一直到终点站的前一站(第n-1站),都满足此规律。现给出的条件是:共有n(n<20)个车站,始发站上车的人数为a,最后一站下车的人数是m(全部下车)。试问从x站开出时车上的人数是多少?

输入:a,n,m和x

输出:x站开出时车上的人数

样例:

输入:5 7 32 4

输出:13

输入

输入:a,n,m和x

输出

输出:x站开出时车上的人数

样例输入

5 7 32 4

样例输出

13

解题思路

设始发站有x人,到达第n站时有m人(第n-1站开出时有m人),不妨设第2站上下车都是y人,那么写一下找规律:

车站 1 2 3 4 5 6 7
人数 x x 2x 2x+y 3x+2y 4x+4y 4x+4y
上车 x y x+y x+2y 2x+3y 3x+5y 5x+8y
下车 0 y y x+y x+2y 2x+3y 3x+5y
x 0 x y x+y x+2y 2x+3y
x 1 0 1 0 1 1 2
y 0 0 0 1 1 2 3

不难发现,之和上下车人数的差等于前两个站那个站上车的人数,其中x的常数和y的常数都是一个斐波拉契数列。只有我们求出这两个常数数组,并计算他们的前缀和,即可知道第k个站开出时的人数。第n-1个站开出时,人数是m,x、以及xy的常数都知道可以求出未知数y,最后代入求解第k个站的人数即可。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,,,,

SSOJ2348火车站(NOIP1998):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter