2469: 【普及-】【P1255】数楼梯

#include<bits/stdc++.h>
using namespace std;
int f[5010],n;
int main(){
    cin>>n;
    f[1]=1;
    f[2]=2;
    for (int i=3;i<=n;i++) {
    	f[i]=f[i-1]+f[i-2];
	}
	cout<<f[n];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define maxn 5000
struct Bigint
{
	int len, a[maxn];
	Bigint(int x = 0)
	{
		memset(a, 0, sizeof(a));
		for (len = 1; x; len++)
			a[len] = x % 10, x /= 10;
		--len;
	}
	int &operator[](int i)
	{
		return a[i];
	}
	void flatten(int L)
	{
		len = L;
		for (int i = 1; i <= L; ++i)
		{
			a[i + 1] += a[i] / 10; a[i] %= 10;
		}
		for (; !a[len];)
			len--;
	}
	void print()
	{
		for (int i = max(len, 1); i >= 1; --i)
			printf("%d", a[i]);
	}
};
Bigint operator+(Bigint a, Bigint b)
{
	Bigint c;
	int len = max(a.len, b.len);
	for (int i = 1; i <= len; ++i)
		c[i] += a[i] + b[i];
	c.flatten(len + 1);
	return c;
}
Bigint operator*(Bigint a, int b)
{
	Bigint c;
	int len = a.len;
	for (int i = 1; i <= len; ++i)
		c[i] = a[i] * b;
	c.flatten(len + 11);
	return c;
}
int N;
int main(){
    cin >> N;
    Bigint f[5010];
    f[1] = Bigint(1);
    f[2] = Bigint(2);
    for (int i = 3; i <= N; i++)
        f[i] = f[i-2] + f[i-1];
    f[N].print();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a,b,c,n;
int main(){
    cin>>n;
    a=1;
    b=2;
    for (int i=3;i<=n;i++) {
    	c=a+b;
    	a=b;
    	b=c;
	}
	cout<<b;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[5000],b[5000],c[5000];//分别作为走一阶和走两阶楼梯的方法数，用字符数组防止溢出 
int main()
{
    int n;
    int x=1;//表示有几位数字，即数字的位数 
 	cin>>n;//表示阶梯数 
    if(n<3)//当只有一阶或者两阶的时候，一阶只有一种方式，两阶有两种走法，所以可以直接输出 
    {
        cout<<n;
        return 0;
    }
    a[1]=1;b[1]=2;//当只有一阶或者两阶的时候，一阶只有一种方式，两阶有两种走法
    
//1.既然太大的数字没有办法直接相加减，那么我们来模拟竖式的算法，逐位相加，满十进一。
//2.好了，那我们用 a，b 两个数组 来存两个加数，用 c 来存答案。
//3.那么就有以下等式 c[i]=a[i]+b[i]，同时我们再判断，如果c[i]>9，那就向高一位进一即可。
//4.用x来就答案的长度，最后输出即可。


 	for(int i=3;i<=n;i++)//当有三个及以上的台阶 ，每多一个台阶都要进行方法数的更新 
    {
        for(int j=1;j<=x;j++)
            c[j]=a[j]+b[j];
        for(int j=1;j<=x;j++)
        {
            if(c[j]>9)//进位 
            {
                c[j+1]+=c[j]/10;
                c[j]%=10;
                if(j==x)  //在最高位c[j]也是大于9的情况下
                    x++;//更新进位数 
            }
        }
        //注意原理是斐波那契数列，所以 
        for(int j=1;j<=x;j++)
            a[j]=b[j];
        for(int j=1;j<=x;j++)
            b[j]=c[j];
    }
 	for(int i=x;i>0;i--)//因为前面逆序相加，所以后面要逆序输出 
        cout<<b[i];
    return 0;
}