P1011 [NOIP1998 提高组] 车站 题解

· · 个人记录

一个纯纯的找规律题。不妨列出几站的上车、下车、车上人数：

站 1 2 3 4 5 6 7 8
上车 a b 1a+1b 1a+2b 2a+3b 3a+5b 5a+8b 8a+13b
下车 / b 0a+1b 1a+1b 1a+2b 2a+3b 3a+5b 5a+8b
车上人数 a a 2a+0b 2a+1b 3a+2b 4a+4b 6a+7b 9a+12b
前两站车上人数的和 / / 2a+0b 3a+0b 4a+1b 5a+3b 7a+6b 10a+11b

观察第一行和第二行a,b前的系数，不难发现符合斐波拉契数列。
并且很明显可以发现第四行a的系数比第三行多1，b的系数比第三行少1。

所以不用管前两行，把第三行直接列出来就行了。 算完这些，b也就能够根据a和m求出来了。很显然，

a\cdot \operatorname{up}[n-1]+b\cdot \operatorname{down}[n-1]=m b = \frac{(m - a \cdot \operatorname{up} [n-1])}{\operatorname{down} [n-1]}

最后答案即为

a\cdot \operatorname{up}[x] + b\cdot \operatorname{down}[x] 
#include <iostream>
using namespace std;
int up[25] = {0, 0, 1, 2}, down[25];
int main() {
    int a, n, m, x;
    cin >> a >> n >> m >> x;
    for(int i = 4; i < n; i ++)
        up [i]  = up  [i - 1] + up  [i - 2] - 1,
        down[i] = down[i - 1] + down[i - 2] + 1;

    int ed = (m - a * up[n - 1]) / down[n - 1];
    cout << a * up[x] + ed * down[x];
}