7.27-7.29
http://acm.zju.edu.cn/show_problem.php?pid=1526http://acm.zju.edu.cn/show_problem.php?pid=1514
http://acm.zju.edu.cn/show_problem.php?pid=1577
http://acm.zju.edu.cn/show_problem.php?pid=1539
http://acm.zju.edu.cn/show_problem.php?pid=1569
http://acm.zju.edu.cn/show_problem.php?pid=1543
http://acm.zju.edu.cn/show_problem.php?pid=1582
http://acm.zju.edu.cn/show_problem.php?pid=1530
http://acm.zju.edu.cn/show_problem.php?pid=1596
http://acm.zju.edu.cn/show_problem.php?pid=1589
http://acm.zju.edu.cn/show_problem.php?pid=1503
http://acm.zju.edu.cn/show_problem.php?pid=1597
http://acm.zju.edu.cn/show_problem.php?pid=1586
http://acm.zju.edu.cn/show_problem.php?pid=1538
http://acm.zju.edu.cn/show_problem.php?pid=1583
http://acm.zju.edu.cn/show_problem.php?pid=1537
http://acm.zju.edu.cn/show_problem.php?pid=1504
http://acm.zju.edu.cn/show_problem.php?pid=1579 1530,可以用深度搜索,广度搜索.但是深度搜索会超时,大家注意啦 1586 最小生成树，因为数据比较大，有教大的优化空间。这是经过第一次优化的程序
00:00.68 2340K
#include<stdio.h>
short int stack,dapter,m,book;
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);
sts=1;
stack=0;
book=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 && dapter]+dapter+m]<max)
{
besti=k;
max=dapter]+dapter+m];
}
book=0;
stack=besti;
cost+=max;
}
printf("%d\n",cost);
}
return 0;
} 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;
const int max=300;
char re;
struct node
{
char c;
int d,up;
};
node w;
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.c='1';
w.d=1;
w.up=-1;
re=1;
do
{
i=w.d*10;
w.d=i%n;
if(re.d]==0)
{
re.d]=1;
w.up=head;
w.c='0';
if(w.d==0) break;
p++;
}
i=w.d*10+1;
w.d=i%n;
if(re.d]==0)
{
re.d]=1;
w.up=head;
w.c='1';
if(w.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.d]=0;
//printf("%d ",n);
for (i=j;i>0;i--)
printf("%c",an);
printf("\n");
}
return 0;
} 1569的做法，如果用穷举，需要计算这么多个数的和：(1+n)*n/2
然后每一个数都进行一次取模运算，可见，n＝1000时肯定超时。
我们可以从最后一个数看起，我们可以得到一个余数，我们记录他。
再看倒数第二个数，我们求出他的余数，这时我们可以计算得到，这个余数A，加上某个余数X，可以被M除进，我们判断这个余数是否存在，这样的余数会大于一个。然后我们把这个余数A进行一些变化保存下来。我们再看倒数第三个数，用上面的方式，不断向前计算。可以得到答案。
源程序：
#include<stdio.h>
int main()
{
int i,j,k,n,m,p;
short intmo,num,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=add-j;
if(p<0)p+=m;
mo++;
}
printf("%d\n",k);
}
return 0;
} 1583 一个超时的程序
ii=m+m+m+m;
ii+=m+m+m+m+m+m+m+m;
ii+=m+m+m+m;
ii=ii/16; 是这个程序
#include<stdio.h>
int m,i,ii,b={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);
for (i=0;i<n;i++)
{
ii=m;
ii=m;
ii=m;
ii=m;
}
for (i=1;i<n-1;i++)
for (j=1;j<n-1;j++)
{
ii=0;
for (u=0;u<n;u++)
for (v=0;v<n;v++)
{
ii+=(m*b);
}
ii=ii/16;
}
for (i=0;i<n;i++)
{
printf("%d",ii);
for (j=1;j<n;j++)
{
printf(" %d",ii);
}
printf("\n");
}
}
return 0;
} 把for (i=1;i<n-1;i++)
for (j=1;j<n-1;j++)
内
换成上面的帖子的部分 就可以过。
主要是
虽然是一个简单的循环，但是增加的计算量是几倍甚至几十倍。
两个循环，9次比较，10多次加法运算。
然后每个数组变量，至少耗费两次乘法一次加法，因为C中，一个变量C的内存地址是这样求得的： C=C+X*N+Y-1;
可见，会有很多个运算在这简单的9个数字的加法中。 快了0.02，第一个是0.27，以下这个是0.25 提高了近10％的运行效率
for (i=1;i<n-1;i++)
{
for (j=1;j<n-1;j++)
{
p=&m;
p2=p+500;
p3=p2+500;
mm=(*(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;
}
}
页:
[1]