程序设计大赛试题

第一题，典型的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

}

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

var a,k:array[0..1000000]of longint

b,c,d,e,f,g,h,i,j,l,n,m,mid:longint

begin

assign(input,'count.in')

assign(output,'count.out')

reset(input)

rewrite(output)

read(b,f)

e:=0

n:=0

l:=1

for c:=1 to b do

begin

read(d)

k[d]:=k[d]+1

end

while l<=b do

begin

for m:=1 to k[n] do

begin

a[l]:=n

l:=l+1

end

n:=n+1

end

e:=0

for c:=1 to b do

begin

i:=c+1

j:=b

while (j>=i) do

begin

mid:=(j+i) div 2

if a[mid]+a[c]>f then j:=mid-1 else i:=mid+1

end

e:=e+(j-c)

end

writeln(e)

close(input)

close(output)

end.

第五届全国ITAT教育工程就业技能大赛复赛试题

C语言程序设计（A卷）

请考生仔细阅读并严格遵守题目中关于文件保存和命名的要求。请务必按照试卷要求为文件命名。 考生答题完毕后，首先创建以“准考证号”命名的文件夹（形式如：433034683），并将考试结果严格按题目上的命名要求进行命名并直接保存在该文件夹下。

注意：考生不得在该文件夹下创建任何子文件夹，所有考试结果均直接保存在该文件夹根目录下。

然后选中整个文件夹，用Winrar压缩工具打包后存放在本考场指定的考试结果存放地址，经监考老师确认上传无误后方可离开考场。

注意：在提交答案时，请务必选中上述存放作品的文件夹（如前面创建的433034683文件夹，而不是文件夹下的全部文件）进行压缩，在完成答案提交后，请确保上述压缩包仍保存在本地计算机中。

请务必按照试卷要求提交指定的文件，不得包含非题目要求的过程文件和临时文件，不得包含本试题文件和试题素材。

注意：凡违反上述规定的考生，其成绩一律按零分处理。

题目命名要求：请将编写好的源程序以题号命名，例如第1题的源程序保存为“1.C” 。

重要提示：由于时间有限，请考生首先保证编写的程序在Wintc环境下可以编译通过并执行，并在此基础上完成考题要求的全部功能，以免因编译不通过影响考生的考试成绩。

1、编程解决如下数学问题：有12升水，怎样利用一个8升和一个5升的容器将水分为两个6升？要求以如下格式打印出分水步骤。（20分）

a12 b8 c5

12 00

*** （ “*”表示当前状态下每个容器的盛水量）

．．．．．．

06 6

2、编程实现：有二维数组a[3][3]={{5.4，3.2，8}，{6，4，3.3}，{7，3，1.3}}，将数组a的每一行元素均除以该行上的主对角元素（第1行同除以a[0][0]，第2行同除以a[1][1]，...）,按行输出新数组。（20分）

3、编程：设x取值为区间[1,20]的整数，求函数f（x）=x-sin（x）- cos（x）的最大值，要求使用自定义函数实现f（x）功能。（20分）

4、编写函数fun，通过指针实现将一个字符串反向。要求主函数输入字符串，通过调用函数fun实现输入字符串反向。（20分）

5、已知学生三门课程基本信息如下。请使用结构体编程，计算学生三门课程平均成绩后，列表输出学生的姓名、数学、英语、计算机、平均分信息，并按平均分排序。（20分）

姓名 数学 英语 计算机

Mary 93100 88

Jone 829090

Peter 917671

Rose 100 8092

6、附加题：编程实现输入一串英文，统计其中各单词出现的个数（不区分大小写字母），以“000”作为字符串输入结束标志，例如：

Twinkle twinkle little star 000（回车）

twinkle little star

2 1 1 （50分）

---