程序设计大赛试题

第一题，典型的BFS找最短路

#include <iostream>

#define MAXN 105

using namespace std

const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}

int m,n

int map[MAXN][MAXN]

int head,tail

int queue[MAXN*MAXN][3]

bool hash[MAXN][MAXN]

int tx,ty

int main()

{

while (cin>>n>>m &&n>0)

{

int i,j,k

memset(map,0,sizeof(map))

cin>>k

while (k--)

{

cin>>i>>j

i--

j--

cin>>map[i][j]

}

memset(hash,true,sizeof(hash))

cin>>queue[0][0]>>queue[0][1]

queue[0][0]--

queue[0][1]--

queue[0][2]=0

hash[queue[0][0]][queue[0][1]]=false

head=0

tail=1

cin>>tx>>ty

tx--

ty--

while (head<tail &&hash[tx][ty])

{

for (k=0k<4k++)

{

i=queue[head][0]+dir[k][0]

j=queue[head][1]+dir[k][1]

while (i>=0 &&i<n &&j>=0 &&j<m &&map[i][j]>0)

{

i+=map[i][j]*dir[k][0]

j+=map[i][j]*dir[k][1]

if (i<0 || i>=n || j<0 || j>=m)

{

if (i<0) i=0

if (i>=n) i=n-1

if (j<0) j=0

if (j>举山=m) j=m-1

break

}

}

if (i>=0 &&i<n &&j>=0 &&j<m)

if (hash[i][j])

{

queue[tail][0]=i

queue[tail][1]=j

queue[tail][2]=queue[head][2]+1

hash[i][j]=false

if (i==tx &&j==ty) cout<<queue[tail][2]<<endl

tail++

}

}

head++

}

if (hash[tx][ty]) cout<<"impossible"<<endl

}

return 0

}

第二题是典型的DP

用f[i][j]表示用前i种币值凑激答悉出总额为j的钱所需的最少钱币个数

状态转移方程f[i][j]=min{f[i-1][j](i>0时),f[i][j-Ki]+1(j>=Ki时),无穷大}

#include <iostream>

#define MAXM 2010

#definme MAXK 15

using namespace std

int m,k

int K[MAXK]

int f[MAXK][MAXM]

int main()

{

while (cin>>m &&m>0)

{

int i,j

cin>>k

for (i=1i<=ki++) cin>>K[i]

memset(f,-1,sizeof(f))

f[0][0]=0

for (i=1i<=ki++)

for (j=0j<=mj++)

{

int min

min=-1

if (f[i-1][j]!=-1 &&(min==-1 || f[i-1][j]<min)) min=f[i-1][j]

if (j>=K[i] &&f[i][j-K[i]]!=-1 &&(min==-1 || f[i][j-K[i]]+1<min)) min=f[i][j-K[i]]+1

f[i][j]=min

}

if (f[k][m]==-1) cout<<"impossible"<<endl

else cout<<f[k][m]<<endl

}

return 0

}

注：题目不难，数据条明乎件也比较松，所以没做什么优化

这个问题看起来不是很简拿态单，需纳敏此要设计一个算法：

先讲数学:

设：

an=a+(n-1)*d （这里d=1）

a1=a

an=a+n-1

sn=(a1+an)n/2=(2a-1+n)/2

再回到这个编程上来：

我们的输入数据其实就是sn，需要找到以a开始的n个连续的递增数列使得和为sn。

这里我们可以用循环来判定，给定一个n，sn已知，就可以求出a，如果a为正整数那么就可以找到等差数列的首项，加上n给定，d=1，那么就可以写出这个和式子。

代码如下：

#include<stdio.h>

void main()

{

int input,i,n,flag

float a//等差数列的首项不一定为整数

flag=0

printf("输入判断的整数:\n")

scanf("%d",&input)

for(n=2n<=inputn++)

{

a=(2*input+n-n*n)/(2.0*n)//求的首项

if(int(a)==a&&a>0)//如果为整整数，则满足要求

{

printf("%d=%d",input,int(a))//输出的序列为整数，a实质是洞迅整数，那么强制转化类型不影响结果

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

printf("+%d",int(a+i))//等差数列的其他项也为整数，a+i实质是整数，装换类型

printf("\n")

flag++//flag记录满足要求的数列数

}

}

if(flag==0)   //flag初始为0，通过上面的循环，如果有满足的在则不为0，为0则说明不能写成等差数列

printf("%d不能被表示成n连续正整数之和\n",input)

}

求黄色这块面积是吧

首先进行一个判断

L/H>=d/D,那么顶面完全黑暗；然后开始着手部分被照亮的情况。

已经知道的是圆柱体侧面积为D*pi*H

顶部面积为 D^2/4*pi

阴影部分面积：码猜d^2/4*pi*(H/(H-L))^2        前提L/H <= d/D

我先带入算一下是不是284：

侧面积=D*pi*H=276；

顶部面积=D^2/4*pi=50；

阴影部分面积：d^2/4*pi*(H/(H-L))^2=42

经过计算276+50-42=284；理论正确燃世之后我们开始加入代码：

#include&ltstdio.h&gt

#include&ltmath.h&gt

#define pi 3.14

struct circle

{

int H,D,d,L//定义好4个数据

int Bigarea()//顶部圆面积

int smallarea()//阴影面积

int cearea()//圆柱侧面积

bool barea()//直接测试阴影是否全部挡住了顶部

circle()

{

H=0D=0d=0L=0

}//构造函数

void setcircle(int,int,int,int)

}

int main()

{

circle A//创建类A

int H,D,L,d

printf("请输入圆柱体的高H：")

scanf("%d",&ampH)

while(!(H&lt1001&amp&ampH&gt0))

{

printf("圆柱体的高必须是0到1001之间,请重新输入：")

scanf("%d",&ampH)

}

printf("请输入圆柱体的直径D：")

scanf("%d",&ampD)

while(!(D&lt1001&amp&ampD&gt0))

{

printf("圆柱体的直径必须是0到1001之间,请重新输入：")

scanf("%d",&ampD)

}

printf("请输入绳子长度L：")

scanf("%d",&ampL)

while(!(L&lt1001&amp&ampL&gt0&amp&ampL&ltH))

{

printf("绳子的长度必须是0到1001之间,并迟段型且比大圆的高H要小请重新输入：")

scanf("%d",&ampL)

}

printf("请输入小圆直径d：")

scanf("%d",&ampd)

while(!(d&lt1001&amp&ampd&gt0&amp&ampd&ltD))

{

printf("圆环半径必须是0到1001之间,并且比大圆D要小请重新输入：")

scanf("%d",&ampd)

}

printf("确认：您输入的数据为：圆柱高度%d，底面直径：%d， 绳子长度：%d ，小圆直径：%d\n",H,D,L,d)

A.setcircle(H,D,d,L)

if ( A.barea())

{

int mianji=A.Bigarea()+A.cearea()-A.smallarea()

printf("您输入的数据处理结果为：%d",mianji)

}

else

{

printf("您输入的数据处理结果为：顶部完全被阴影所遮挡住了！\n")

}

}

int circle::Bigarea()

{

return (D/2)*(D/2)*pi

}

int circle::smallarea()

{

return (d/2)*(d/2)*pi*H*H/(H-L)/(H-L)

}

int circle::cearea()

{

return pi*D*H

}

void circle::setcircle(int a,int b,int c,int d)

{

H=aD=bthis-&gtd=cL=d

}

bool circle::barea()

{

if(L/H &ltd/D)

return true

else

return false

}本来想在修改一下，结果已经提交的代码不能改，你先复制过去运行一下看看，我都已经注释了、

---