Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:我这个题目TLE了,测试数据都是对的,就是TLE,请教哪里可以优化下,我实在是看不出来了!谢谢In Reply To:我这个题目TLE了,测试数据都是对的,就是TLE,请教哪里可以优化下,我实在是看不出来了!谢谢 Posted by:dljlw at 2007-07-13 22:18:43 > #include<stdio.h> > #include<string.h> > #include<stdlib.h> > > struct Element > { > int r[501]; > }e[501]; > > int compare(int *b,int k,int *c,int l) > { > int i,mark=1; > for(i=0;i<k;i++)if(b[i]!=c[i])break; > for(;i<k;i++){if(b[i]<c[i]){mark=0;break;}else break;} > return mark; > } > > void add(int *b,int k,int *c,int l) > { > int i,j,z,d[501],e[501],f[501]; > memset(f,0,sizeof(f)); > int w=z=k>l?k:l; > for(i=0;i<k;i++)d[i]=b[i]; > for(i=0;i<l;i++)e[i]=c[i]; > int t=0; > for(--w,i=k-1,j=l-1;w>=0;w--) > { > f[w]=b[i--]+c[j--]+t; > if(i<0){i=0;b[i]=0;} > if(j<0){j=0;c[j]=0;} > t=f[w]/10; > f[w]=f[w]%10; > } > if(t)f[0]=f[0]+t*10; > if(k<l) > { > for(i=-1;i<l-k;i++)printf(" "); > for(i=0;i<k;i++)printf("%d",d[i]);printf("\n"); > printf("+"); > for(i=0;i<l;i++)printf("%d",e[i]);printf("\n"); > for(i=-1;i<z;i++)printf("-");printf("\n"); > } > else > { > printf(" "); > for(i=0;i<k;i++)printf("%d",d[i]);printf("\n"); > for(i=0;i<k-l;i++)printf(" ");printf("+"); > for(i=0;i<l;i++)printf("%d",e[i]);printf("\n"); > for(i=-1;i<z;i++)printf("-");printf("\n"); > } > if(!t)printf(" "); > for(i=0;i<z;i++)printf("%d",f[i]);printf("\n"); > } > > void sub(int *b,int k,int *c,int l) > { > int i,j,z,t,d[501],e[501],f[501]; > memset(f,0,sizeof(f)); > int w=z=k>l?k:l; > t=0; > for(i=0;i<k;i++)d[i]=b[i]; > for(i=0;i<l;i++)e[i]=c[i]; > if(k>l) > { > t=1; > for(--w,i=k-1,j=l-1;w>=0;w--) > { > if(b[i]<c[j]){b[i]=10+b[i];b[i-1]--;} > f[w]=b[i--]-c[j--]; > if(i<0){i=0;b[i]=0;} > if(j<0){j=0;c[j]=0;} > if(f[w]<0)b[i]--; > } > for(i=0;i<k;i++)printf("%d",d[i]);printf("\n"); > for(i=0;i<k-l-1;i++)printf(" ");printf("-"); > for(i=0;i<l;i++)printf("%d",e[i]);printf("\n"); > for(i=0;i<k;i++)printf("-");printf("\n"); > } > else if(k==l) > { > if(compare(b,k,c,l)) > { > t=1; > for(--w,i=k-1,j=l-1;w>=0;w--) > { > if(b[i]<c[j]){b[i]=10+b[i];b[i-1]--;} > f[w]=b[i--]-c[j--]; > if(i<0){i=0;b[i]=0;} > if(j<0){j=0;c[j]=0;} > } > } > else > for(--w,i=l-1,j=k-1;w>=0;w--) > { > if(c[i]<b[j]){c[i]=10+c[i];c[i-1]--;} > f[w]=c[i--]-b[j--]; > if(i<0){i=0;c[i]=0;} > if(j<0){j=0;b[j]=0;} > } > printf(" "); > for(i=0;i<k;i++)printf("%d",d[i]);printf("\n"); > printf("-"); > for(i=0;i<l;i++)printf("%d",e[i]);printf("\n"); > for(i=0;i<k+1;i++)printf("-");printf("\n"); > } > else > { > for(--w,i=l-1,j=k-1;w>=0;w--) > { > if(c[i]<b[j]){c[i]=10+c[i];c[i-1]--;} > f[w]=c[i--]-b[j--]; > if(i<0){i=0;c[i]=0;} > if(j<0){j=0;b[j]=0;} > } > for(i=-1;i<l-k;i++)printf(" "); > for(i=0;i<k;i++)printf("%d",d[i]);printf("\n"); > printf("-"); > for(i=0;i<l;i++)printf("%d",e[i]);printf("\n"); > for(i=0;i<l+1;i++)printf("-");printf("\n"); > } > for(i=0;i<z;i++)if(f[i])break;else printf(" "); > if(!t)printf("-"); > for(;i<z;i++)printf("%d",f[i]);printf("\n"); > } > > void mul(int *b,int k,int *c,int l) > { > int i,j,z,q,p,f[501],len,w; > memset(f,0,sizeof(f)); > for(i=0;i<l;i++)printf(" "); > for(i=0;i<k;i++)printf("%d",b[i]);printf("\n"); > for(i=0;i<k-1;i++)printf(" ");printf("*"); > for(i=0;i<l;i++)printf("%d",c[i]);printf("\n"); > for(i=l-1;i>=0;i--) > { > p=0;z=q=l-1-i; > if(c[i]==0) > { > if(i==l-1){for(j=0;j<k-1;j++)printf(" ");for(j=0;j<l+1;j++)printf("-");printf("\n");} > for(len=0;len<l+k-z-1;len++)printf(" ");printf("0\n"); > continue; > } > for(j=k-1;j>=0;j--) > { > int t=c[i]*b[j]+p; > e[i].r[q++]=t%10; > p=t/10; > } > if(p)e[i].r[q++]=p; > if(i==l-1) > { > w=(l+1)>q?(l+1):q; > for(len=0;len<l+k-w;len++)printf(" "); > for(len=0;len<w;len++)printf("-");printf("\n"); > } > for(len=0;len<l+k-q;len++)printf(" "); > for(j=q-1;j>=z;j--)printf("%d",e[i].r[j]);printf("\n"); > } > len=0; > for(j=0;j<q;j++) > { > for(i=l-1;i>=0;i--) > { > f[len]+=e[i].r[j]; > } > f[len+1]=f[len]/10; > f[len]=f[len]%10; > len++; > } > if(l!=1) > { > for(i=len;i<w;i++)printf(" "); > for(i=len-1;i>=0;i--)printf("-");printf("\n"); > for(i=len;i<w;i++)printf(" "); > for(i=len-1;i>=0;i--)printf("%d",f[i]);printf("\n"); > } > } > > int main() > { > int n,i,k,l; > scanf("%d",&n); > while(n--) > { > char a[501],ch; > k=l=0; > scanf("%s",a); > int b[501],c[501]; > for(i=0;i<501;i++) > {memset(e[i].r,0,sizeof(struct Element));} > for(i=0;a[i];i++) > { > if(a[i]=='+' || a[i]=='-' || a[i]=='*'){ch=a[i];break;} > b[k++]=(int)(a[i]-'0'); > } > for(i++;a[i];i++) > { > c[l++]=(int)(a[i]-'0'); > } > if(ch=='+')add(b,k,c,l); > if(ch=='-')sub(b,k,c,l); > if(ch=='*')mul(b,k,c,l); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator