大数加法（SDUT“斐波那契”串）4335

时间：2023-03-09 00:07:02
大数加法（SDUT“斐波那契”串）4335

题目链接：https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2697/pid/4335.html

具体思路：倒着相加，具体看代码

AC代码：

#include<iostream>

#include<stack>

#include<iomanip>

#include<stdio.h>

#include<cmath>

#include<algorithm>

#include<string>

#include<cstring>

#include<queue>

using namespace std;

# define ll long long

# define maxn 100000+1999

# define inf 0x3f3f3f3f

int a[maxn];

int b[maxn];

int temp[maxn];

int ans[maxn];

int main()

{

    ios::sync_with_stdio(false);

    int n;

    cin>>n;

    memset(temp,0,sizeof(temp));

    memset(a,0,sizeof(a));

    memset(b,0,sizeof(b));

    int t1=1,t2=1;

    a[1]=1;

    b[1]=1;

    temp[1]=1;

    ans[1]=1;

    ans[2]=1;

    int p=2;

    while(p<=n+100)

    {

        int len=max(t1,t2);

        for(int i=1; i<=len; i++)

        {

            temp[i]+=a[i];

            temp[i+1]+=temp[i]/10;

            temp[i]=temp[i]%10;

        }

        if(temp[len+1]!=0)

            len++;

        for(int i=len; i>=1; i--)

        {

            ans[p+len-i+1]=temp[i];

            a[i]=b[i];

            b[i]=temp[i];

        }

        p+=len;

        t1=t2;

        t2=len;

    }

    cout<<ans[n]<<endl;

    return 0;

}

相关文章