Burnling's Blog
0%

斐波那契数列（加强版

发表于 更新于

  • 这题（指P1255）卡得我挺难受的（指WA，TLE，MLE都出来了）

  • 题目很简单就是个斐波那契数列

  • 重点是数据范围$N<=5000$这真的不会累死人吗

  • 这么大的数据自然该想到用高精度

    以及不能用递归（因为存在大量重复运算，$O(n^2)$的时间复杂度可不是闹着玩的）要用递推

程序分析

  1. 高精度部分

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    struct BigNum{
    	int len;
    	int d[5000];
    }A[3];

    bool cmp(BigNum a,BigNum b){
    	if(a.len!=b.len) return a.len>b.len;
    	for(int i = 0;i<a.len;i++){
    		if(a.d[i]!=b.d[i]) return a.d[i]>b.d[i];
    	}
    	return true;
    }

    BigNum operator+(const BigNum a,const BigNum b){
    	BigNum t;
    	memset(t.d,0,a.len+5);
    	for(int i = 0;i<=b.len;i++){
    		t.d[i] = a.d[i] + b.d[i];
    	}
    	for(int i = 0;i<=b.len;i++){
    		if(t.d[i]>=10){
    			t.d[i] -= 10;
    			t.d[i+1] += 1;
    		}
    	}
    	if(t.d[b.len]!=0){
    		t.len = b.len+1;
    	}else{
    		t.len = b.len;
    	}
    	return t;
    }

    void output(BigNum a){
    	for(int i = a.len-1;i>=0;i--){
    		printf("%d",a.d[i]);
    	}
    }

    BigNum只开到3的原因是要用到滚动数组否则会MLE

    （其实这段没什么主要就是把高精加搬过来了）

    以及一个运算符重载

    我个人认为这里的运算符重载完全可以被替换掉

    1
    2
    BigNum operator+(const BigNum a,const BigNum b);
    BigNum add(BigNum a,BigNum b);

  2. 递推部分

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    int main(){
    	int n;
    	scanf("%d",&n);
    	
    	A[1].d[0] = 1;
    	A[1].len = 1;
    	A[2].d[0] = 2;
    	A[2].len = 2;
    	if(n<3){
    		printf("%d",n);
    		return 0;
    	}
    	for(int i = 3;i<=n;i++){
    		A[0] = A[1];
    		A[1] = A[2]; 
    		A[2] = A[0] + A[1];
            //滚动数组
    	}
    	output(A[2]);
    	return 0;
    }