2021.07.26 P1011 车站（斐波那契数列）

2021.07.26 P1011 车站（斐波那契数列）

[P1011 NOIP1998 提高组] 车站 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.改变形式的斐波那契数列。

题意：

第一站只上人，第二站上下车人数一样多，第三站到第(n-1)站上车人数是前两站之和，下车人数与前一站上车人数相同。

分析：

设第一站上x1人，第二站上x2人。

\[第一站：上：x1；下：0，净上：x1
\\
第二站：上：x2；下：x2；净上：0
\\
第三站：上：x1+x2；下：x2；净上：x1
\\
第四站：上：x1+2*x2；下：x1+x2；净上：x2
\\
第五站：上：2*x1+3*x2；下：x1+2*x2；净上：x1+x2
\\
第六站：上：3*x1+5*x2；下：2*x1+3*x2；净上：x1+2*x2
\\
…
\]

以此类推。

对于x1，从第五站开始变为规律的斐波那契数列，对于x2，从第四站开始变为规律的斐波那契数列。

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,a,x,x1[25],x2[25];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

int main(){

	a=read();n=read();m=read();x=read();

	x1[1]=x1[3]=x1[5]=x1[6]=1;

	x2[4]=x2[5]=1;

	int x1i=0,x2i=0;

	for(int i=1;i<min(n,7);i++)x1i+=x1[i],x2i+=x2[i];

	for(int i=7;i<n;i++)x1[i]=x1[i-1]+x1[i-2],x1i+=x1[i];

	for(int i=6;i<n;i++)x2[i]=x2[i-1]+x2[i-2],x2i+=x2[i];

	int b=(m-a*x1i)/x2i;

	x1i=x2i=0;

	for(int i=1;i<=x;i++)x1i+=x1[i],x2i+=x2[i];

	//cout<<a<<" "<<x1i<<" "<<b<<" "<<x2i<<endl;//

	cout<<a*x1i+b*x2i;

	return 0;

}

2021.07.26 P1011 车站（斐波那契数列）的相关教程结束。