最后两个点错了

P1303 A*B Problem

hexuchen @ 2023-07-16 14:17:31

最后两个点错了，怀疑是数组开太小，但开大了又MLE 提交记录1：

提交记录2：

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s,s2;
    int a[2001],b[2001],c[2001][12001],d[100001],ans=0,sum,ji=0,k,abc=100001;
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    memset(c,0,sizeof c);
    memset(d,0,sizeof d);
    cin>>s>>s2;
    if(s=="0" ||s2=="0"){
        cout<<0;
        return 0;
    }
    for(int i=s.size()-1;i>=0;i--){
        a[ans]=s[i]-'0';
        ans++;
    }
    ans=0;
    for(int i=s2.size()-1;i>=0;i--){
        b[ans]=s2[i]-'0';
        ans++;
    }
    for(int j=0;j<201;j++){
        for(int i=0;i<201;i++){
            sum=b[i]*a[j]+ji;
            ji=0;
            if(sum<10){
                c[j][i+j]=sum;
                continue;
            }
            ji=sum/10;
            sum%=10;
            c[j][i+j]=sum;
        }
    }
    ji=0;
    sum=0;
    for(int i=0;i<201;i++){
        for(int j=0;j<101;j++){
            sum+=c[j][i];
        }
        sum+=ji;
        if(sum<10){
            d[i]=sum;
            ji=0;
            sum=0;
            continue;
        }
        ji=sum/10;
        sum%=10;
        d[i]=sum;
        sum=0;
    }
    while(d[abc]==0){
        abc--;
    }
    for(int i=abc;i>=0;i--){
        cout<<d[i];
    }
    return 0;
}

by rnf5114 @ 2023-07-16 14:18:53

@hexuchen c数组为啥开2维

by hexuchen @ 2023-07-16 14:20:01

@rnfmabj5114 我的思路是模拟竖式

by hexuchen @ 2023-07-16 14:21:57

@rnfmabj5114 c数组就是算式结果

by hexuchen @ 2023-07-16 14:22:30

@rnfmabj5114 但模拟竖式结果是1行1行的，就用2维

by rnf5114 @ 2023-07-16 14:22:56

@hexuchen 竖式这题做不了吧

by hexuchen @ 2023-07-16 14:27:59

@rnfmabj5114 可以吧，那你是怎么做的

by Max6700 @ 2023-07-16 14:31:11

@hexuchen 思路：正常输入字符串，倒序根据字符和数字的互换存入数组，按位计算（注意进位），清前导零，输出

代码：

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

string A,B;

int a[100000],b[100000],c[4000010];

int main(){

    cin>>A>>B;

    for(int i=A.length()-1,j=1;i>=0;i--,j++)
        a[j]=A[i]-'0';

    for(int i=B.length()-1,j=1;i>=0;i--,j++) 
        b[j]=B[i]-'0';

    for(int i=1;i<=B.length();i++)
    {
        for(int j=1;j<=A.length();j++)
        {
            c[i+j-1]+=a[j]*b[i];
        }
    }

    for(int i=1;i<A.length()+B.length();i++)
    {
        c[i+1]+=c[i]/10;
        c[i]%=10;
    }

    int len=4000010;
    while(!c[len] && len>1)
    {
        len--;
    }

    for(int i=len;i>=1;i--)
        cout<<c[i];

    return 0;
}

我才不会告诉你这是lg课程教的

by rnf5114 @ 2023-07-16 14:31:59

@hexuchen 你竖式炸内存了

by hexuchen @ 2023-07-24 16:58:40

懂

|