60分,死于后两个点(我可能要恨死高精度)

P1303 A*B Problem

Cyan_rose @ 2018-07-11 11:23:42

咳咳。。最近死在高精度上花了两三天了居然还没通,好不容易过了加减又死于乘法。。这次60分错在后两个点,问题是。。为什么第四个点我的输出和标答只!差!一!位!

我的是 7072111534......

标答是 7072110534......

???(一脸问号) 当然第五个点就更不知道了。。

代码在下面

#include<bits/stdc++.h>
using namespace std;
const int N=10e4+5;
const int M=100;
struct Ks{
    int id;
    int cj;
}ks[N];
int a,b,c,d,e,f,g,xi,i2,xj,j2,a1[N],a2[M],a4[N],a5[N],deep=1,tot,sum,cnt,cntt,mx,my,mmx,mmy,mmmx,mmmy,zz,bj,lj,jt,flag;
char b1[N],b2[N],b3[25005][1005],b4[N],ljj[N],bc1,bc2;
int main()
{
//freopen("water.in","r",stdin);
//freopen("water.out","w",stdout);
int k;
cin>>b1>>b2;
b=strlen(b1),c=strlen(b2);
if(b<c)
swap(b1,b2),swap(b,c);
cntt=1;
cnt=0;
tot=1;
if(b1[0]=='0'){cout<<0;return 0;}
if(b2[0]=='0'){cout<<0;return 0;}

if(b==1&&c==1)
{
    int kk=b1[0]-48,kkk=b2[0]-48;
    cout<<kk*kkk;return 0;
}

for(int i=b-1;i>=0;i--)
{
for(int j=c-1;j>=0;j--)
{
//  cout<<"b3["<<i+1<<"]["<<j+1<<"]="<<b3[i+1][j+1]<<endl;

if((b1[i]-48)*(b2[j]-48)+b3[i+1][j+1]<=9)
{
//  cout<<"first"<<endl;
//  cout<<"b1["<<i<<"]="<<b1[i]<<endl<<"b2["<<j<<"]="<<b2[j]<<endl;
    b3[i+1][j+1]=b3[i+1][j+1]+(b1[i]-48)*(b2[j]-48)+48;
//  cout<<"b3["<<i+1<<"]["<<j+1<<"]="<<b3[i+1][j+1]<<endl;
    }
else
{
    //cout<<"second"<<endl;
    int k=(b1[i]-48)*(b2[j]-48);
    while(k>=0)
    {
        k-=10;
        cnt++;
    }
    //cout<<"k="<<k<<endl<<"cnt="<<cnt<<endl<<"b3["<<i+1<<"]["<<j+1<<"]="<<b3[i+1][j+1]<<" "<<b3[i+1][j+1]+1-1<<endl;;
    b3[i+1][j+1]=b3[i+1][j+1]+k+10+48;//cout<<"b3["<<i+1<<"]["<<j+1<<"]="<<b3[i+1][j+1]<<" "<<b3[i+1][j+1]+1-1<<endl;
    if(b3[i+1][j+1]>=58)b3[i+1][j]=b3[i+1][j]+1,b3[i+1][j+1]-=10;//cout<<"b3["<<i+1<<"]["<<j<<"]="<<b3[i+1][j]<<" "<<b3[i+1][j]+1-1<<endl;;
    //cout<<"b3["<<i+1<<"]["<<j+1<<"]="<<b3[i+1][j+1]<<" "<<b3[i+1][j+1]+1-1<<endl;
    b3[i+1][j]=b3[i+1][j]+cnt-1;
    //cout<<"b3["<<i+1<<"]["<<j<<"]="<<b3[i+1][j]<<" "<<b3[i+1][j]+1-1<<endl;
    cnt=0;
    //cout<<"b3["<<i+1<<"]["<<j<<"]="<<b3[i+1][j]<<" "<<b3[i+1][j]+1-1<<endl;
}

}
}

for(int i=b;i>=0;i--)
{for(int j=c;j>=0;j--)
{if(b3[i][j]<='0')b3[i][j]+=48;
if(b3[i][j]==58)b3[i][j-1]++,b3[i][j]-=10;
}
}

for(int i=b;i>=0;i--)
{for(int j=c;j>=0;j--)
{
    b3[i][j+i]=b3[i][j],b3[i][j]=48;
}}

for(int i=0;i<=b+c;i++)
{for(int j=0;j<=b+c;j++)
{if(b3[i][j]==0)b3[i][j]=48;
if(b3[i][j]==96)b3[i][j]=48;
//cout<<b3[i][j];
}
//cout<<endl;
}

for(int i=1;i<=b+c;i++)
{

    for(int j=b+c;j>=0;j--)
    {if(b3[i][j]+b3[i-1][j]-96>=0&&b3[i][j]+b3[i-1][j]-96<=9)
    {b3[i][j]=b3[i][j]+b3[i-1][j]-48;
}
    else
    if(b3[i][j]+b3[i-1][j]-96>9)
    {b3[i][j]=b3[i][j]+b3[i-1][j]-58;
    b3[i][j-1]++;
    k=i;
    while(b3[i][b+c-k-1]-48>=10)
    {b3[i][b+c-k-1]-=10;
    if(b-k-2>=0)b3[i][b-k-2]++;
    else {b3[i][j-1]=1,lj=1;}
    k++;
    }
}

}

}

for(int i=0;i<=b+c;i++)
{
if(b3[b+c][i]!='0')
a1[i]=b3[b+c][i]-48,lj=1,cout<<a1[i];
if(b3[b+c][i]=='0'&&lj==1)
a1[i]=b3[b+c][i]-48,cout<<a1[i];
}
return 0;

return 0;
//fclose(stdin);
//fclose(stdout);
}

p.s:楼主蒟蒻所以代码显得很奇怪。。。不过我觉得没什么毛病~


by king_more @ 2018-07-14 18:04:00

我觉得楼主的代码也没有毛病,就是看不懂


by mabangjie @ 2018-07-17 10:43:26

可以AC

#include<bits/stdc++.h>
using namespace std;
char a[9999],b[9999];
int  n[3000],m[3000],S[3000];
int  main()
{
    int w=0,k=0;
    cin>>a>>b;
    int lena=strlen(a);
    int lenb=strlen(b);
    for(int i=0;i<lena;i++)
       n[i]=a[lena-i-1]-'0';
    for(int i=0;i<lenb;i++)
       m[i]=b[lenb-i-1]-'0';
    for(int i=0;i<lena;i++)
     for(int j=0;j<lenb;j++)
     {
        S[i+j]+=n[i]*m[j];
        if(S[i+j]!=0)
          w=i+j;
     }
    for(int i=0;i<=w+5;i++)
    {
       S[i+1]+=S[i]/10;
       S[i]%=10;
       if(S[i]!=0)
         k=i;
    }
    for(int i=k;i>=0;i--)
       cout<<S[i];
    return 0;
}

by mabangjie @ 2018-07-17 10:44:53

???????? ? 代码 ? ? 巨长 ? ????????


by Cyan_rose @ 2018-07-18 16:57:01

@mabangjie 谢谢大佬代码。话说高精度乘法一般都是您这个格式,转存为一般的数组做吗?(我字符数组直接计算就出问题了。。)


by mabangjie @ 2018-07-18 20:57:42

高精度的四则运算框架都一样

只是中间的模拟竖式算法部分不同

都只要用一维数组

(其实我也是最近学的)


by mabangjie @ 2018-07-18 20:59:24

用数组计算很复杂

字符可以转换成数


by mabangjie @ 2018-07-19 13:15:14

说错了


by Cyan_rose @ 2018-07-19 14:47:26

ok,受教了,谢谢大佬~


by Cyan_rose @ 2018-07-19 14:54:34

对了大佬,还有个小问题,处理进位那一步的时候为什么循环次数是w+5?


by 爱挨打的豆豆 @ 2018-07-25 14:52:00

~~** _ 哈哈哈(路过)

_ **~~


|