洛谷千题详解 | P1011 [NOIP1998 提高组] 车站【C++、Java、Pascal语言】

博主主页：Yu·仙笙

 

专栏地址：洛谷千题详解

目录

题目描述

输入格式

输出格式

输入输出样例

解析：

C++源码：

C++源码2：

C++源码3：

Pascal源码：

Java源码：

---

------------------------------------------------------------------------------------------------------------------------------- 

 ------------------------------------------------------------------------------------------------------------------------------- 

题目描述

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

 ------------------------------------------------------------------------------------------------------------------------------- 

输入格式

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

 ------------------------------------------------------------------------------------------------------------------------------- 

输出格式

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

 ------------------------------------------------------------------------------------------------------------------------------- 

输入输出样例

输入 #1

5 7 32 4

输出 #1

13

 ------------------------------------------------------------------------------------------------------------------------------- 

解析：

第一站：上车 a 人；车上有 a 人；

第二站：假设上车 u 人，则下车 u 人；车上仍然是a人；

第三站：上车人数等于前两站上车人数之和：a+u 人，下车人数等于上次上车人数 u 人；净上车人数为 a 人；车上有 2a 人；

第四站：上车人数 =a+2u，下车人数 =a+u；净上车人数 =u；车上有多少人呢？就是 2a+u；

第五站：上车人数 =2a+3u，下车人数 =a+2u，净上车人数=a+u；车上有3a+2u 人；

第六站：上车人数 =3a+5u，下车2a+3u 人，净上车人数 =a+2u；车上有 4a+4u 人……

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

将第三站净上车人数看作x1，第四站看作x2，第五站为x3，第六站为x4，有 x1+x2=x3, \ x2+x3=x4…这不是斐波那契数列么？

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

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

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

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

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

同样的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）还是需要分类讨论的

 ------------------------------------------------------------------------------------------------------------------------------- 

C++源码：

 #include
    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;
    } 

 ------------------------------------------------------------------------------------------------------------------------------- 

C++源码2：

#include
#include//两句以include开头的，是文件头。用途是把其他的程序段连接到这个程序，从而得到更多函数的运用。
using namespace std;//打了这段话时，大家就可以创建函数了（当然我没用函数）
int a,n,m,x,f[25],sc[25];//这是全局变量。定义的有：题目所述的a、n、m、x,和存放从每一个车站开出后的人数，和每一个车站的上车人数。 
int main()//定义主函数（main不要打错^_^） 
{
  scanf("%d%d%d%d",&a,&n,&m,&x);//scanf是一个可以用比较快的速度读入数据的函数。读入n。（需要打文件#include）
  if(x==n){printf("0");return 0;}//判断，如果要求的车站是终点站，那就直接输出0。（printf和scanf通常配套使用） 
  f[1]=f[2]=sc[1]=a;//赋值。第一站和第二站开出时的人数和第一站上车的人数都是a。 
  for(int i=0;i<=m;i++)//由于我们不知道第二站上车的人数，所以我们可以枚举第二站上车的人数，从而找出正确答案。 
  {
    sc[2]=i;//把第二站上车的人数设为当前模拟的值。 
	for(int j=3;j//从第三站开始模拟到第n-1站。（由于终点站开出时没有人，所以不模拟） 
    {
      sc[j]=sc[j-1]+sc[j-2];//根据题目所述求出当前上车的人数。 
      f[j]=f[j-1]+sc[j]-sc[j-1];//再求出当亲车站开出后的人数。 
    }
    if(f[n-1]==m)//如果第n-1站开出后的人数是m，就可以结束枚举了。（因为终点站下车的人数刚好是m） 
    {printf("%d",f[x]);return 0;}//输出要求的车站开出后车上面的人数，然后结束主函数。 
  }
  return 0;//其实这句话可以省略。（以防万一嘛^_^） 
}

 ------------------------------------------------------------------------------------------------------------------------------- 

C++源码3：

#include
using namespace std;
long long a,n,m,x;
long long on[100000],off[100000],now[100000];//上车人数，下车人数，车上现在人数
int main(){
    long long i,j;
    cin>>a>>n>>m>>x;
    on[1]=a; off[1]=a;
    for(i=0;;i++){
        on[2]=i; now[2]=a;
        for(j=3;j<=n-1;j++){
            on[j]=on[j-1]+on[j-2];
            off[j]=on[j-1];
            now[j]=now[j-1]+on[j]-off[j];
        }
        if(now[n-1]==m){
            cout<
            break;
        }
    }
    return 0;
}

 ------------------------------------------------------------------------------------------------------------------------------- 

Pascal源码：

var
 a1,b1,i,j,n,m,k,t,max:longint;
 a,b:array[1..25] of longint;
begin
  read(a1,n,m,k);
  a[1]:=1;
  a[2]:=0;
  b[1]:=0;
  b[2]:=1;//初始化
  for i:=3 to n do
   begin
   a[i]:=a[i-1]+a[i-2];
   b[i]:=b[i-1]+b[i-2];//建造表格
   end;
  if n=1 then 
         begin
         write(m);//n=1时特别注意
         exit;
         end;
  b1:=(m-(a[n-1]+1)*a1) div (b[n-1]-1);//最后一个下车数为前一个车站的总人数
  write((a[k]+1)*a1+(b[k]-1)*b1);
end.

 ------------------------------------------------------------------------------------------------------------------------------- 

Java源码：

import java.util.Scanner;
 
public class P1017 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final char[] num = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};
        char[] ans = new char[1000];
        int temp, i = 0;
        int n = sc.nextInt();
        int R = sc.nextInt();
        temp = n;
 
        while (n != 0) {
            int mod = n % R;
            int t = n / R;
            if (mod < 0) {
                mod -= R;
                t++;
            }
            n = t;
            ans[i++] = num[mod];
        }
 
        System.out.print(temp + "=");
        for (int j = i - 1; j >= 0; j--)
            System.out.print(ans[j]);
        System.out.print("(base" + R + ")");
    }
}
 

 -------------------------------------------------------------------------------------------------------------------------------