Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:我这个题目TLE了,测试数据都是对的,就是TLE,请教哪里可以优化下,我实在是看不出来了!谢谢

Posted by huang03jun at 2009-05-20 23:50:59 on Problem 1396
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator