60分求救

P1255 数楼梯

lguo @ 2022-08-02 15:07:31

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n;
int a[1000001],b[10000001],c[10000001];
int l1,l2,l3;

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    if(n==1||n==2)
    {
        cout<<n;
        return 0;
    }
    a[1]=1;
    b[1]=2;
    l1=1;
    l2=1;
    for(int i=3;i<=n;i++)
    {
        l3=max(l1,l2);
        memset(c,0,sizeof(c));
        for(int j=1;j<=l3;j++)
        {
            c[j]+=a[j]+b[j];
            c[j+1]+=c[j]/10;
            c[j]%=10;
        }
        while(c[l3+1]!=0)
            l3++;

        for(int j=l2;j>=1;j--)
            a[j]=b[j];
        l1=l2;
        for(int j=l3;j>=1;j--)
            b[j]=c[j];
        l2=l3;
    }
    for(int i=l3;i>=1;i--)
        cout<<c[i];
    return 0;
}

自学的高精度,找不出哪里错了。求众巨佬帮帮忙!


by lilong @ 2022-08-02 15:25:58

@lguo 把第25行删掉,28行改为

c[j]=a[j]+b[j]

然后全部都加完后再处理进位,就能AC了


by lilong @ 2022-08-02 15:27:53

@lguo c 的长度有 10000000,每次初始化 memset 的时间复杂度都为 O(n),会超时。所以直接计算即可,但如果计算和进位混在一起就会出问题


by lguo @ 2022-08-02 15:33:20

@lilong 好的,谢谢您,我再试试。


by lguo @ 2022-08-02 15:35:57

@lilong 万分感谢,已AC


|