第五个点TLE求助！

CZ_7 @ 2021-08-26 16:03:03

#include<bits/stdc++.h>
using namespace std;
int n;
string ans="1",s1;
string jia(string a,string b){
    string over="";
    int c=max(a.length(),b.length());
    for(int i=a.length();i<c;i++)a='0'+a;
    for(int i=b.length();i<c;i++)b='0'+b;
    int flag=0;
    for(int i=c-1;i>=0;i--){
        if(a[i]+b[i]+flag-'0'-'0'<=9){
            int shu=a[i]+b[i]+flag-'0'-'0';
            flag=0;
            over=to_string(shu)+over;
        }
        else{
            int shu=a[i]+b[i]+flag-'0'-'0'-10;
            flag=1;
            over=to_string(shu)+over;
        }
    }
    if(flag==1)over="1"+over;
    return over;
}
string yiweicheng(string a,char b){
    string over="";
    int flag=0;
    for(int i=a.length()-1;i>=0;i--){
        int shu=((a[i]-'0')*(b-'0')+flag)%10;
        int kk=((a[i]-'0')*(b-'0')+flag)/10;
        flag=kk;
        over=to_string(shu)+over;
    }
    if(flag>0)over=to_string(flag)+over;
    return over;
}
string cheng(string a,string b){
    string c="",d="";
    for(int i=0;i<b.length();i++){
        d=yiweicheng(a,b[i]);
        for(int j=1;j<b.length()-i;j++){
            d=d+"0";
        }
        c=jia(c,d);
    }
    return c;
}
int main(){
    string a,b;
    cin>>a>>b;
    if(a=="0"||b=="0"){
        cout<<"0";
        return 0;
    }
    cout<<cheng(a,b);
    return 0;
}

by int4096 @ 2021-08-26 16:07:24

我的代码：（用python他不香吗）

a=int(input());
b=int(input());
print(a*b);

by 奥斯卡小冰人 @ 2021-08-26 16:10:37

捞捞

by 奥斯卡小冰人 @ 2021-08-26 16:11:06

别沉

by CZ_7 @ 2021-08-26 16:11:19

@int4096

，，，但是比赛不让用呀

by tlzhy @ 2021-08-26 16:11:29

下一个

by 10circle @ 2021-08-26 17:50:53

@CZ_7 你这份代码是 O(n^3) 的。

over=to_string(shu)+over;一句需要先将to_string(shu)+over计算出来，再将它复制给over，复杂度是 O(n) 的。d=d+"0";也类似，时间复杂度为 O(n)。

建议不要这么写高精度，使用string类型反而不好写。先将数字的每一位拆开，存入整型数组的方式更好写而且常数小。

同时我建议在 OI 中不要使用string，使用char类型数组会更方便且常数更小。

我按照你的思路写的代码：

#include<bits/stdc++.h>
using namespace std;

const int N=4005;

char s1[N],s2[N];
int a[N],b[N],ans[N],c[N],anslen;

int main(){
    scanf("%s%s",s1,s2);
    int n=strlen(s1),m=strlen(s2);
    for(int i=0;i<n;i++)a[n-i-1]=s1[i]-'0';
    for(int i=0;i<m;i++)b[m-i-1]=s2[i]-'0';
    // 低位在前方便处理 
    for(int i=0;i<m;i++){
        for(int j=0;j<i;j++)c[j]=0;//前i位为0
        for(int j=0;j<n;j++)c[j+i]=a[j]*b[i];
        int len=i+n+2;
        for(int j=0;j<=len;j++)c[i+1]+=c[i]/10,c[i]%=10;//进位 
        while(len>0&&c[len]==0)len--;

        anslen=max(len,anslen);
        for(int j=0;j<=anslen;j++)ans[j]+=c[j];
        for(int j=0;j<=anslen;j++)ans[j+1]+=ans[j]/10,ans[j]%=10;
        anslen++;
        while(anslen>0&&ans[anslen]==0)anslen--;
    }
    for(int i=anslen;i>=0;i--)cout<<ans[i];
    return 0;
}

by 10circle @ 2021-08-26 17:58:29

以及这题有更简单的做法，为什么要用这种（

by 奥斯卡小冰人 @ 2021-08-27 07:26:26

@10circle stO 10circle

by yu_666 @ 2021-08-27 15:53:49

@CZ_7 开启O2优化

by CZ_7 @ 2021-08-28 23:13:09

@yu_666

应该不是O2就能解决的，不过谢谢