算法学习
Luogu P1601 A+B Problem(高精)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
|
t=(a[i]+b[i]-'0'-'0'+t)/10;
#include<bits/stdc++.h>
using namespace std;
int main(){ string a,b; cin>>a>>b; reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); int t=0; string s; int i=0; for(i=0;i<min(a.size(),b.size());++i){ s+=to_string((a[i]+b[i]-'0'-'0'+t)%10); t=(a[i]+b[i]-'0'-'0'+t)/10; } for(int j=i;j<max(a.size(),b.size());++j){ if(a.size()>b.size()){ s+=to_string((a[j]-'0'+t)%10); t=(a[j]-'0'+t)/10; } else if(a.size()<b.size()){ s+=to_string((b[j]-'0'+t)%10); t=(b[j]-'0'+t)/10; } } if(t!=0)s+=to_string(t); reverse(s.begin(),s.end()); cout<<s; return 0; }
#include<bits/stdc++.h>
using namespace std; int a[550],b[550],c[550]; int la,lb,lc;
int main(){ string ma,mb; cin>>ma>>mb; la=ma.size(); lb=mb.size(); lc=max(la,lb); for(int i=0;i<la;++i) a[i]=ma[la-i-1]-'0'; for(int i=0;i<lb;++i) b[i]=mb[lb-i-1]-'0'; int t=0; for(int i=0;i<lc;++i){ c[i]=(a[i]+b[i]+t)%10; t=(t+a[i]+b[i])/10; } if(t){ c[lc] = t; lc++; } for(int i=lc-1;i>=0;--i){ cout<<c[i]; } return 0; }
|
Luogu P2142 高精度减法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
|
bool cmp(int a[],int b[]){ if(la!=lb) return la<lb; for(int i=la;i;--i){ if(a[i]!=b[i]) return a[i]<b[i]; } return false; }
#include<bits/stdc++.h>
using namespace std; #define N 10100 int a[N],b[N],c[N]; int la,lb,lc;
bool cmp(int a[],int b[]){ if(la!=lb)return la<lb; for(int i=la;i>0;--i){ if(a[i]!=b[i])return a[i]<b[i]; } return false; }
void sub(int a[],int b[],int c[]){ for(int i=1;i<=lc;++i){ if(a[i]<b[i]){ a[i+1]--; a[i]+=10; } c[i]=a[i]-b[i]; } while(c[lc]==0&&lc>1)lc--; } int main(){ string ma,mb; cin>>ma>>mb; la=ma.size(); lb=mb.size(); for(int i=1;i<=la;++i){ a[i]=ma[la-i]-'0'; } for(int i=1;i<=lb;++i){ b[i]=mb[lb-i]-'0'; } lc=max(la,lb); if(cmp(a,b)){ cout<<"-"; swap(a,b); } sub(a,b,c); for(int i=lc;i>0;--i){ cout<<c[i]; } return 0; }
|
Luogu P1303 A*B Problem
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
|
1 2 3 × 4 5 ------- 1 5 (3×5) 1 0 (2×5, 左移一位) 0 5 (1×5, 左移两位) ------- 1 2 (3×4, 左移一位) 0 8 (2×4, 左移两位) 0 4 (1×4, 左移三位) ------- 5 5 3 5
void mul(int a[],int b[],int c[]){ for(int i=1;i<=la;i++){ for(int j=1;j<=lb;++j){ c[i+j-1]+=a[i]*b[j] } } for(int i=1;i<lc;++i){ c[i+1]+=c[i]/10; c[i]%=10; } while(c[lc]==0&&lc>1) lc--;去除前导0 }
#include<bits/stdc++.h>
using namespace std; int la,lb,lc; int a[2020],b[2020],c[4000010];
int main(){ string ma,mb; cin>>ma>>mb; la=ma.size(); lb=mb.size(); lc=la+lb; for(int i=1;i<=la;++i) a[i]=ma[la-i]-'0'; for(int i=1;i<=lb;++i) b[i]=mb[lb-i]-'0'; for(int i=1;i<=la;++i){ for(int j=1;j<=lb;++j){ c[i+j-1]+=a[i]*b[j]; } } for(int i=1;i<lc;++i){ c[i+1]+=c[i]/10; c[i]%=10; } while(c[lc]==0 &&lc>1) lc--; for(int i=lc;i>=1;--i){ cout<<c[i]; } return 0; }
|
Luogu P1480 A/B Problem