7.27-7.29

sheep426 · 发表于 2005-7-27 12:58

小康 · 发表于 2005-7-28 00:05

1530,可以用深度搜索,广度搜索.但是深度搜索会超时,大家注意啦

小康 · 发表于 2005-7-28 17:06

1586 最小生成树，因为数据比较大，有教大的优化空间。这是经过第一次优化的程序

00:00.68 2340K
#include<stdio.h>
short int stack[1000],dapter[1000],m[1000][1000],book[1000];
int main()
{
int i,j,k,n,cases,sts,besti,max,cost;
freopen("in.txt","r",stdin);
scanf("%d",&cases);
while(cases--)
{
scanf("%d",&n);
for (i=0;i<n;i++)
{
scanf("%d",&dapter);
book=1;
}
for (i=0;i<n;i++)
for (j=0;j<n;j++)
scanf("%d",&m[j]);
sts=1;
stack[0]=0;
book[0]=0;cost=0;
for (i=1;i<n;i++)
{
max=1000000;
for (j=0;j<sts;j++)
for (k=0;k<n;k++) if(book[k] && dapter[stack[j]]+dapter[k]+m[stack[j]][k]<max)
{
besti=k;
max=dapter[stack[j]]+dapter[k]+m[stack[j]][k];
}
book[besti]=0;
stack[sts++]=besti;
cost+=max;
}
printf("%d\n",cost);
}
return 0;
}

小康 · 发表于 2005-7-28 17:37

1530的做法
搜索。
从第一位开始搜索，每一位的数字，不是0，就是1。
假设n＝3，第一位搜索1，余数是1，第二位搜索1，余数是2 11mod3=2,第二位搜索0，余数是1，
11 mod 3 =0
10 mod 3=1
这是，就有深度广度搜索的问题了。假设我们用深度。
我们第二位搜索1，接着搜索第三位，111％3＝0 我们找到了我们要的答案。这是我们可以发现，每次搜索，余数肯定<n，如果出现之前已经搜索过的余数，那肯定是白费力气了。我们发现一个剪枝条件。
搜索73，77的时候，我们发现程序计算很久。其实，因为用深度搜索不好，因为这样可能搜索到的答案，是一个很大的数，很多位的数。
我们用广度。第二位，搜索11，10，我们把他压如队列。接着，搜索11，10，我们把111，110，101，100压入队列，同时，对余数重复也进行判断，这样我们可以得到一个很快的广度有限搜索算法

#include<stdio.h>
char an[300];
const int max=300;
char re[10000];
struct node
{
char c;
int d,up;
};
node w[max];
int main()
{
int i,j,k,n,dep,head,p;
for (i=0;i<10000;i++) re=0;
freopen("in.txt","r",stdin);
k=0;
while(scanf("%d",&n),n)
{
dep=0;
head=0;
p=1;
w[0].c='1';
w[0].d=1;
w[0].up=-1;
re[1]=1;
do
{
i=w[head].d*10;
w[p].d=i%n;
if(re[w[p].d]==0)
{
re[w[p].d]=1;
w[p].up=head;
w[p].c='0';
if(w[p].d==0) break;
p++;
}
i=w[head].d*10+1;
w[p].d=i%n;
if(re[w[p].d]==0)
{
re[w[p].d]=1;
w[p].up=head;
w[p].c='1';
if(w[p].d==0) break;
p++;
}
head++;
}while(head<=p);

i=p;
j=0;
do
{
an[++j]=w.c;
i=w.up;

}while(i!=-1);
for (i=1;i<=p;i++)
re[w.d]=0;
//printf("%d ",n);
for (i=j;i>0;i--)
printf("%c",an);
printf("\n");
}
return 0;
}

小康 · 发表于 2005-7-28 17:44

1569的做法，如果用穷举，需要计算这么多个数的和：(1+n)*n/2
然后每一个数都进行一次取模运算，可见，n＝1000时肯定超时。

我们可以从最后一个数看起，我们可以得到一个余数，我们记录他。
再看倒数第二个数，我们求出他的余数，这时我们可以计算得到，这个余数A，加上某个余数X，可以被M除进，我们判断这个余数是否存在，这样的余数会大于一个。然后我们把这个余数A进行一些变化保存下来。我们再看倒数第三个数，用上面的方式，不断向前计算。可以得到答案。

源程序：

#include<stdio.h>
int main()
{
int i,j,k,n,m,p;
short int mo[5000],num[10000],add;
freopen("in.txt","r",stdin);
while(scanf("%d %d",&n,&m)!=EOF)
{
for (i=0;i<m;i++) mo=0;
for (i=0;i<n;i++)
{
scanf("%d",&num);

}
k=0;
j=0;

for (i=n-1;i>-1;i--)
{
add=num%m;

if(add==0) k++;
j+=add;
while(j>m) j-=m;
p=m-j;
if(j==0) p=0;
k+=mo[p];
p=add-j;
if(p<0)p+=m;
mo[p]++;
}
printf("%d\n",k);
}
return 0;
}

小康 · 发表于 2005-7-28 19:45

1583 一个超时的程序
ii[j]=m[i-1][j-1]+m[i-1][j]+m[i-1][j]+m[i-1][j+1];
ii[j]+=m[j-1]+m[j-1]+m[j]+m[j]+m[j]+m[j]+m[j+1]+m[j+1];
ii[j]+=m[i+1][j-1]+m[i+1][j]+m[i+1][j]+m[i+1][j+1];
ii[j]=ii[j]/16;

小康 · 发表于 2005-7-28 19:46

是这个程序
#include<stdio.h>
int m[500][500],i[500][500],ii[500][500],b[3][3]={1,2,1,2,4,2,1,2,1};
int main()
{
int i,j,k,n,cases,u,v;
cases=0;
freopen("in.txt","r",stdin);
while(scanf("%d",&n),n)
{
printf("Case %d:\n",++cases);
for (i=0;i<n;i++)
for (j=0;j<n;j++)
scanf("%d",&m[j]);
for (i=0;i<n;i++)
{
ii[0]=m[0];
ii[n-1]=m[n-1];
ii[0]=m[0];
ii[n-1]=m[n-1];
}
for (i=1;i<n-1;i++)
for (j=1;j<n-1;j++)
{
ii[j]=0;
for (u=0;u<n;u++)
for (v=0;v<n;v++)
{
ii[j]+=(m[i+u-1][j+v-1]*b[v]);
}
ii[j]=ii[j]/16;
}
for (i=0;i<n;i++)
{
printf("%d",ii[0]);
for (j=1;j<n;j++)
{
printf(" %d",ii[j]);

}
printf("\n");
}

}

return 0;
}

小康 · 发表于 2005-7-28 19:49

把for (i=1;i<n-1;i++)
for (j=1;j<n-1;j++)
内
换成上面的帖子的部分就可以过。
主要是
虽然是一个简单的循环，但是增加的计算量是几倍甚至几十倍。
两个循环，9次比较，10多次加法运算。
然后每个数组变量，至少耗费两次乘法一次加法，因为C中，一个变量C[X][Y]的内存地址是这样求得的： C[X][Y]=C[0][0]+X*N+Y-1;
可见，会有很多个运算在这简单的9个数字的加法中。

小康 · 发表于 2005-7-28 20:39

快了0.02，第一个是0.27，以下这个是0.25 提高了近10％的运行效率

for (i=1;i<n-1;i++)
{

for (j=1;j<n-1;j++)
{
p=&m[i-1][j];
p2=p+500;
p3=p2+500;

mm[j]=(*(p-1)+*p+*p+*(p+1)+*(p2-1)+*(p2-1)+*(p2)+*(p2)+*(p2)+*(p2)+*(p2+1)+*(p2+1)+*(p3-1)+*p3+*p3+*(p3+1))/16;

}

}

		自动登录	找回密码
密码			加入后院