P1011 [NOIP1998 提高组] 车站

【题目描述】

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

输入格式：

输入只有一行四个整数，分别表示始发站上车人数 a ，车站数 n，终点站下车人数 m 和所求的站点编号 x 。

输出格式：

输出一行一个整数表示答案：从 x 站开出时车上的人数。

输入样例：5 7 32 4

输出样例：13

数据范围：1≤a≤20，1≤x≤n≤20，1≤m≤2e4。

【题解】

读题：已经知道 a, n, m, x，但是第二站上下车人数不定，假设第二站上车人数为 b ，列出下表；

车站编号	1	2	3	4	5	6	7	x	n-1	n
上车人数 up[i]	a	b	a+b	a+2b	2a+3b	3a+5b	5a+8b			0
下车人数 down[i]	0	b	a	b	a+b	3b	3a+5b			m
两者差值 dis[i]	a	0	b	a+b	a+2b	2a+3b	3a+5b
发车人数 f[i]	a	a	2a	2a+b	3a+2b	4a+4b	6a+7b		m

两种方式第一种，暴力枚举 b，理论上 b的取值范围为 [0,inf]，这种方法有点取巧和作弊了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+1;
int up[N], down[N], f[N];
int main_ac(){
//    freopen("data.in", "r", stdin);
    int a,n,m,x; cin>>a>>n>>m>>x;
    up[1]=a; down[1]=0;
    for(int b=0; ; b++){
        up[2]=down[2]=b;
        for(int i=3; i<=n; i++){
            up[i]=up[i-1]+up[i-2];
            down[i]=up[i-1];
        }
        f[1]=a;
        for(int i=2; i<=n; i++){
            f[i]=f[i-1] + up[i]-down[i];
        }
        if(f[n-1]==m) {
            cout<<f[x]; break;
        }
    }
    return 0;
}

第二种，找规律，解出 b

发车人数 f[i]：a  a  2a  2a+b  3a+2b  4a+4b  6a+7b  9a+12b  14a+20b ....   m
提取 f[i]的系数：10 10 20 21 32 44 67 9,12 14,20 ...
找到规律,当：
a 的系数，A[i]=A[i-1]+A[i-2]-1  //此处归纳得出，还需证明
b 的系数，B[i]=B[i-1]+B[i-2]+1

所以 x 站台的发车人数 f[x]=A[x]*a+B[x]*b
n-1 站台的发车人数 f[n-1]=A[n-1]*a+B[n-1]*b=m
解出 b=(m-A[n-1]*a)/B[n-1];
从而得到 f[x]

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+1;
int A[N], B[N], F[N];
int main(){
//    freopen("data.in", "r", stdin);
    int a,n,m,x; cin>>a>>n>>m>>x;
    A[1]=A[2]=1, A[3]=2;
    B[1]=B[2]=B[3]=0;
    for(int i=4; i<=n-1; i++){
        A[i]=A[i-1]+A[i-2]-1;//此处归纳得出，还需证明
        B[i]=B[i-1]+B[i-2]+1;
    }
    int b=(m-A[n-1]*a)/B[n-1];//推导公式
    F[x]=A[x]*a+B[x]*b;
    cout<<F[x];
    return 0;
}