题解 P1011 【车站】

xiejinhao · 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;
}

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

再次使用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年更新），本人已经删除最初版源码，有任何其他问题可以直接私信。

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

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

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