做了一个高精度的题(http://www.vijos.cn/Problem_Show.asp?id=1040),一开始用了普通的模拟法,最后一个超大数据超时,因此对程序进行了全面优化,优化后的程序全部 0ms AC

#include<stdio.h>
#include<string.h>
int a[2505],b[2505],x[5010]={0}; /*开大几位,避免越界*/
int main(void)
{
int i,j,k;
int lena,lenb;
char temp[10010];
int t;
scanf("%s",temp);
lena=strlen(temp); /*减少下面的循环中判断计算(最多可以减少10000次计算)*/
if(lena%4)
{
t=4-lena%4;
for(i=t+lena-1;i>=t;i--) temp[i]=temp[i-t];
temp[t+lena]='\0';
lena+=t;
for(i=0;i<t;i++) temp[i]='0';
}
for(i=0,j=1;i<lena;i+=4,j++)
a[j]=(temp[i]-'0')*1000+(temp[i+1]-'0')*100+(temp[i+2]-'0')*10+temp[i+3]-'0';
lena=j;
scanf("%s",temp);
lenb=strlen(temp); /*减少下面的循环中判断计算(最多可以减少10000次计算)*/
if(lenb%4)
{
t=4-lenb%4;
for(i=t+lenb-1;i>=t;i--) temp[i]=temp[i-t];
temp[t+lenb]='\0';
lenb+=t;
for(i=0;i<t;i++) temp[i]='0';
}
for(i=0,j=1;i<lenb;i+=4,j++)
b[j]=(temp[i]-'0')*1000+(temp[i+1]-'0')*100+(temp[i+2]-'0')*10+temp[i+3]-'0';
lenb=j;
for(i=lena-1;i>0;i--)
for(j=lenb-1;j>0;j--)
{
t=i+j; /*临时计算,最多减少7500次计算*/
x[t]+=a[i]*b[j];
x[t-1]+=x[t]/10000; /*使用万进制,计算速度加快4倍*/
x[t]=x[t]%10000; /*使用万进制,计算速度加快4倍*/
}
while(!x[i]) i++;
printf("%d",x[i]);
i++;
for(;i<lena+lenb-1;i++)
if(x[i]>1000) printf("%d",x[i]);
else
if(x[i]>100) printf("0%d",x[i]);
else
if(x[i]>10) printf("00%d",x[i]);
else
printf("000%d",x[i]);
return 0;
}