首页 > 分享 > A + B = C（字符串模拟手写string）

A + B = C（字符串模拟手写string）

花匠小妙招
2024-11-26 04:26

original link - http://acm.hdu.edu.cn/showproblem.php?pid=6646

题意：

给出 a , b , c → a ∗ 1 0 x + b ∗ 1 0 y = c ∗ 1 0 z a,b,cto a*10^x+b*10^y=c*10^z a,b,c→a∗10x+b∗10y=c∗10z，求 x , y , z x,y,z x,y,z。

解析：

显然 a ∗ 1 0 x , b ∗ 1 0 y a*10^x,b*10^y a∗10x,b∗10y中一个数与 c ∗ 1 0 z c*10^z c∗10z同位数，或至少一位。模拟一边减法，看看是不是可以整数另外一个得到 1 0 k 10^k 10k。

不知道是不是hdu的锅，虽然代码涉及 s t l   s t r i n g stl ;string stlstring但是常数非常小，一直 T L E TLE TLE。

自己手写了一个 s t r i n g string string就过去了，明明时间复杂度都是 O ( n ) O(n) O(n)。。。

手写string：

struct String{ char x[maxn]; char& operator[](int idx){ return x[idx]; } char operator[](int idx)const{ return x[idx]; } int len=0; void reverse(){ char tmp; for(int i=0,j=len-1;i<j;i++,j--){ tmp=x[i],x[i]=x[j],x[j]=tmp; } } void operator+=(char ch){ x[len++]=ch; x[len]=''; } void substr(int pos){ int i; for(i=0;pos<len;i++,pos++){ x[i]=x[pos]; } x[len=i]=''; } void operator=(const char *it){ len=0; while((*it)!=''){ x[len++]=*it; it++; } x[len]=''; } void operator=(const String&p){ len=p.len; for(int i=0;i<len;i++)x[i]=p.x[i]; x[len]=''; } };

12345678910111213141516171819202122232425262728293031323334353637383940

代码：

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+9; struct String{ char x[maxn]; char& operator[](int idx){ return x[idx]; } char operator[](int idx)const{ return x[idx]; } int len=0; void reverse(){ char tmp; for(int i=0,j=len-1;i<j;i++,j--){ tmp=x[i],x[i]=x[j],x[j]=tmp; } } void operator+=(char ch){ x[len++]=ch; x[len]=''; } void substr(int pos){ int i; for(i=0;pos<len;i++,pos++){ x[i]=x[pos]; } x[len=i]=''; } void operator=(const char *it){ len=0; while((*it)!=''){ x[len++]=*it; it++; } x[len]=''; } void operator=(const String&p){ len=p.len; for(int i=0;i<len;i++)x[i]=p.x[i]; x[len]=''; } }res,a,b,c,tmp; void sub(const String &x,const String &y){ if(x.len<y.len){res="-1";return;} if(x.len==y.len){ for(int i=0;i<x.len;i++){ if(x[i]>y[i])break; if(x[i]<y[i]){res="-1";return;} } } res=""; int i,j; int f=0; for(i=x.len-1,j=y.len-1;i>=0,j>=0;i--,j--){ if(x[i]-f>=y[j]){ res+='0'+x[i]-f-y[j]; f=0; } else{ res+='0'+x[i]-f+10-y[j]; f=1; } } for(;i>=0;i--){ res+=x[i]-f;f=0; } res.reverse(); for(i=0;i<res.len&&res[i]=='0';i++); if(i==res.len)res="0"; else res.substr(i); //cout<<"res is "<<res<<endl; } int compare(const String &p){ int x,y; int ctx=0,cty=0; for(x=p.len-1;p[x]=='0';x--,ctx++); for(y=res.len-1;res[y]=='0';y--,cty++); if(x!=y)return -1e9; for(int i=0;i<=x;i++){ if(res[i]!=p[i])return -1e9; } return cty-ctx; } int main(){ int t;scanf("%d",&t); while(t--){ scanf("%s%s%s",a.x,b.x,c.x); a.len=strlen(a.x); b.len=strlen(b.x); c.len=strlen(c.x); int cta=0,ctb=0,ctc=max(0,max(a.len,b.len)-c.len+2); for(int i=1;i<=ctc;i++) c+='0'; tmp=a; cta=c.len-a.len-1; for(int i=1;i<=cta;i++) tmp+='0'; sub(c,tmp); if(res[0]!='-'&&res[0]!='0'){ int ans=compare(b); if(ans!=-1e9){ if(ans>=0){ printf("%d %d %dn",cta,ans,ctc); continue; } else{ printf("%d %d %dn",cta-ans,0,ctc-ans); continue; } } } tmp+='0';cta++; sub(c,tmp); if(res[0]!='-'&&res[0]!='0'){ int ans=compare(b); if(ans!=-1e9){ if(ans>=0){ printf("%d %d %dn",cta,ans,ctc); continue; } else{ printf("%d %d %dn",cta-ans,0,ctc-ans); continue; } } } tmp=b; ctb=c.len-b.len-1; for(int i=1;i<=ctb;i++) tmp+='0'; sub(c,tmp); if(res[0]!='-'&&res[0]!='0'){ int ans=compare(a); if(ans!=-1e9){ if(ans>=0){ printf("%d %d %dn",ans,ctb,ctc); continue; } else{ printf("%d %d %dn",0,ctb-ans,ctc-ans); continue; } } } tmp+='0';ctb++; sub(c,tmp); if(res[0]!='-'&&res[0]!='0'){ int ans=compare(a); if(ans!=-1e9){ if(ans>=0){ printf("%d %d %dn",ans,ctb,ctc); continue; } else{ printf("%d %d %dn",0,ctb-ans,ctc-ans); continue; } } } printf("-1n"); } }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173