自动搬运

查看原文

来自洛谷，原作者为

	xiejinhao 人间总有一两风，填我十万八千梦

搬运于2025-08-24 21:19:54，当前版本为作者最后更新于2019-04-05 01:32:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P1011 车站 题解 绝非正解

没做的先看看思路，别急着看代码

严正声明：禁止抄袭本题解

---

• 在做之前，我们先找找规律：

1. 第一站：上车 $a$ 人；车上有 $a$ 人；
2. 第二站：假设上车 $u$ 人，则下车 $u$ 人；车上仍然是 $a$ 人；
3. 第三站：上车人数等于前两站上车人数之和：$a+u$ 人，下车人数等于上次上车人数 $u$ 人；净上车人数为 $a$ 人；车上有 $2a$ 人；
4. 第四站：上车人数 $=a+2u$，下车人数 $=a+u$；净上车人数 $=u$；车上有多少人呢？就是 $2a+u$；
5. 第五站：上车人数 $=2a+3u$，下车人数 $=a+2u$，净上车人数 $=a+u$；车上有 $3a+2u$ 人；
6. 第六站：上车人数 $=3a+5u$，下车 $2a+3u$ 人，净上车人数 $=a+2u$；车上有 $4a+4u$ 人……

这里不必在列下去了，发现规律了吗？

将第三站净上车人数看作 $x_1$，第四站看作 $x_2$，第五站为 $x_3$，第六站为$x_4$，有 $x_1+x_2=x_3, \ x_2+x_3=x_4…$ 这不是斐波那契数列么？

• 知道了起始人数 $a$，知道了终止人数，这里的 $u$ 就可求了； 不过计算机不认识方程，所以我们要想个办法：

• 把 $a$ 和 $u$ 分开处理！！！

---

我们不妨把每一站中 $a$ 的关系看作 $a$ 的斐波那契数列，而 $u$ 的关系看作 $u$ 的斐波那契数列。

• 由于是从第三站开始出现了这样的规律，所以第一项为第三站，第二项就是第四站

我们不妨自己再次总结 $a$ 的规律，于是得到下面的代码:

int p = 1, q = 0, k = 0, sum1 = 0;
for(int i = 1; i <= n - 5; i++) {
	k = p + q;
	sum1 += k;
	p = q;
	q = k;
}

常规斐波那契就不解释了，但注意，这里统计的 $sum1$ 是 $a$ 的系数！

细心的小伙伴就会发现了，这里满足的条件是 $n>5$，其实 $n≤5$ 也可以，但是代码较为复杂，后面说；

且注意：第三项 $a$ 的系数为 $1$，第四项为 $0$，所以定义 p = 1，q = 0； 这里 sum1 = sum1+2（从第五项开始计算，前面还有 $2a$，不能忽略）

• 同样的，我们得到了计算 $u$ 系数的代码

int e = 0, t = 1, g = 0, sum2 = 0;
for(int i = 1; i <= n - 5; i++) {
	g = e + t;
	sum2 += g;
	e = t;
	t = g;
}

同样的 sum2=sum2+1；（第五项开始算，前面还有一个 $u$） 那么 $u=?$ 这个大家自己思考，后面给代码再给答案.

---

• 以上内容针对 $n>5$，那么我们就可以较为整齐地处理 $n≤5$ 的情况了。

这个如何处理？

大家思考一下，根据我们列出的上面的式子，车站数是肯定 $≥2$ 的，车最少要经过两站。那么无论 $n=2$ 还是 $3$，输出的不都是 $a$ 么？后面的大家自己推理；

• 那么对于 $n≤5$ 也讨论完了，对于 $n>5$ 呢？

这时又与 $x$ 有关了，根据上面推导的斐波那契数列的规律，那到第 $x$ 站的 $a$ 有几个？$u$ 有几个？（人数 $=t×a+i×u$）还是需要分类讨论的，没有做的思考一下，再看下面代码：

if(x <= 5) {
	if(x == 1 || x == 2)cout << ？;
	else if(x == 3)cout << ？;
	else if(x == 4)cout << ？;
	else if(x == 5)cout << ？;
} else {
	for(int i = 1; i <= x - ？; i++) {
		k = p + q;
		sum1 += k;
		p = q;
		q = k;
	}
	sum1 += 2;
	for(int i = 1; i <= x - ？; i++) {
		g = e + t;
		sum2 += g;
		e = t;
		t = g;
	}
	sum2 += 1;
}

这里的“？”是什么供大家思考，最后会给出源码，参考以上的推导。

$\texttt{Update} \ 2019.7.23\&2023.10.20$

再次使用LaTeX进行了渲染优化了码风，删除了部分内容，附上高清无码完整代码：

    #include<cstdio>
    using namespace std;
    int a, n, m, x, u=1, z, y;
    int main()
    {
        scanf("%d %d %d %d", &a, &n, &m, &x); 
        if(n <= 5) {
            if(n == 2||n == 3)
                printf("%d", a);
            else if(n == 4) {
                if(x == 1 || x == 2) printf("%d", a);
                else if(x == 3) printf("%d", a * 2);
            }
            else if(n == 5) {
                if(x == 1 || x == 2) printf("%d", a);
                else if(x == 3) printf("%d", a * 2);
                else if(x == 4) 
                    printf("%d", (m - a * 3) / 2 + a * 2);
            }
        }
        else {
            int p = 1, q = 0, k = 0, sum1 = 0;
            for(int i = 1; i <= n - 5; i++) { 	
                k = p + q;
                sum1 += k;
                p = q;
                q = k;
            }
            int s1 = sum1 + 2;
            int e = 0, t = 1, g = 0,sum2 = 0;
            for(int i = 1; i <= n - 5; i++) {
                g = e + t;
                sum2 += g;
                e = t;
                t = g;
            }
            int s2 = sum2 + 1;
            int S = (m - s1 * a) / s2;
            q = k = e = g = sum1 = sum2 = 0;
            p = t = 1;
            if(x <= 5) {
                if(x == 1 || x == 2) printf("%d", a);
                else if(x == 3)  printf("%d", a * 2);
                else if(x == 4) printf("%d", S + a * 2);
                else printf("%d", S * 2 + a * 3);
            }
            else {
                for(int i = 1; i <= x - 4; i++) {
                    k = p + q;
                    sum1 += k;
                    p = q;
                    q = k;
                }
                sum1 += 2;
                for(int i = 1; i <= x - 4; i++) {
                    g = e + t;
                    sum2 += g;
                    e = t;
                    t = g;
                }
                sum2 += 1;
                printf("%d", sum1 * a + sum2 * S);
            }
        }
        return 0;
    } 

不给代码感觉还是不太好？$orz$

不知道大家看到这里是否清晰呢？不清楚可以评论，代码还有待优化，欢迎大家提出意见~

本人在文末最后声明一次：代码中加入问号本意是希望大家多思考，最后已经给出完整代码（2019年更新），本人已经删除最初版源码，有任何其他问题可以直接私信。

辛苦管理再次审核一下了……

最后声明：禁止抄袭本题解

第一篇题解，虽然写的不好，但看我这么辛苦，不点个赞再走吗？