LFYZ-OJ ID: 1024 火车站

2022-11-27 22:42:33

火车过站

问题描述

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

输入

输入包含一行，有四个正整数：a（a<=100），n（n<=20），m（m<=10000）和p（p<=19）

输出

输出为一个整数，为p站开出时车上的人数。

输入样例

1 6 7 3

输出样例

分析

思路1

最容易想到的方法就是枚举。枚举第二站上、下车的人数，然后根据题目给出的递推关系判断是否正确。这里的递推关系很清晰，要注意数据规模。

思路2

递推。我们把每站上、下车的人数和上、下车后的总人数用一张表列出来：

车站：    1         2       3        4          5           ……

总数：    a         a       2a      2a+x        3a+2x       ……

上：      a         x       a+x     a+2x        2a+3x       ……

下：      0         x       x       a+x         a+2x        ……

一种简单的方法是根据这个规律使用计算机进行模拟公式计算，我们可以定义一个结构体类型来表示公式，也可以使用数组，这里使用结构体是为了表达更清晰：

struct gs{

    int a;      //a的个数

    int x;      //x的个数   公式=ka+jx

}

struct {

    gs up;      //上的人数

    gs down;    //下的人数

    gs rs;      //上、下车后的总人数

}Chezhan[21];

看懂了吗，现在你可以使用循环模拟上面的上、下车过程。

Chezhan[i].up=Chezhan[i-1].up+Chezhan[i-2].up;

Chezhan[i].down=Chezhan[i-1].up;                //这样用要使用运算符重载

最后你得到的一个公式是：ka+jx=m，k和j的值在过程中可以计算出来，m和a是已知的。求解x的过程中如果可以除尽，说明有有效值。如果(m-ka)%j!==0，说明除不尽，答案为No Answer.。有了x的值，代入p号站的rs公式中即可得到结果。代码例程1说明了计算过程。

思路3

这里提供另外一种方法，是对斐波那契数列相关属性的运用。通过公式的推导，可以最大可能的提高运算效率。这里涉及到的数列属性最好能够记下来。查看yuyanggo的专栏：NOIP1998火车站。代码见例程2。

代码例程1

#include<iostream>

using namespace std;

struct gs{                                  //定义公式结构体

	int a;

	int x;

};

struct{                                     //定义车站数组

	gs rs;

	gs up;

	gs down;

}INFO[21];

int main(){

	int a, n, m, p, x;

	scanf("%d%d%d%d", &a, &n, &m, &p);

	INFO[1].up.a=1;                         //初始信息

	INFO[2].up.x=1;

	INFO[2].down.x=1;

	INFO[1].rs.a=1;

	INFO[2].rs.a=1;

	for(int i=3; i<n; i++){                 //在循环中递推

		INFO[i].up.a=INFO[i-1].up.a+INFO[i-2].up.a;

		INFO[i].up.x=INFO[i-1].up.x+INFO[i-2].up.x;

		INFO[i].down.a=INFO[i-1].up.a;

		INFO[i].down.x=INFO[i-1].up.x;

		INFO[i].rs=INFO[i-1].rs;

		INFO[i].rs.a+=INFO[i].up.a;

		INFO[i].rs.a-=INFO[i].down.a;

		INFO[i].rs.x+=INFO[i].up.x;

		INFO[i].rs.x-=INFO[i].down.x;

		//printf("%d*a+%d*x\n", INFO[i].rs.a, INFO[i].rs.x);调试代码，输出过程中数据

	}

	if((m-INFO[n-1].rs.a*a)%INFO[n-1].rs.x){//x不能整除，无答案

		printf("No answer.");

		return 0;

	}else{                                  //x可以被整除

		x=(m-INFO[n-1].rs.a*a)/INFO[n-1].rs.x;

		printf("%d", INFO[p].rs.a*a+INFO[p].rs.x*x);

	}

	return 0;

}

代码例程2

#include <iostream>

using namespace std;

int b[20]={0,1,1};                              //斐波那契数列

int main(){

  int a,n,m,x,i,k=0;

  scanf("%d%d%d%d",&a,&n,&m,&x);

  if(x==1){

    printf("%d",a);

    return 0;

  }

  for(i=3;i<20;i++) b[i]=b[i-1]+b[i-2];         //计算斐波那契数列

  if(n>4)   k=(m-(b[n-3]+1)*a)/(b[n-2]-1);

  printf("%d",(b[x-1]-1)*k+(b[x-2]+1)*a);

  return 0;

}

码农公寓