程序设计大赛试题

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

}

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

现在网上有许多题库，大多是可以在线评测，所以叫做Online Judge。除了USACO是为IOI准备外，其余几乎全部是大学的ACM竞赛题库。

USACO

http://ace.delos.com/usacogate

美国著名在线题库，专门为信息学竞赛选手准备

TJU

http://acm.tongji.edu.cn/

同济大学在线题库，唯一的中文题库，适合NOIP选手

ZJU

http://acm.zju.edu.cn/

浙江大学在线题库

JLU

http://acm.jlu.edu.cn/

吉林大学在线题库（一直上不去）

PKU

http://acm.pku.edu.cn

北京大学在线题库

URAL

http://acm.timus.ru

俄罗斯乌拉尔大学在线题库

SGU

http://acm.sgu.ru/

俄罗斯圣萨拉托夫州大学在线题库

ELJ

http://acm.mipt.ru/judge/bin/problems.pl?lang=en

俄罗斯莫斯科物理技术学院

SPOJ

https://spoj.sphere.pl/

波兰格但斯克理工大学

UVA

http://acm.uva.es/

西班牙的Universidad de Valladolid在线题

ACM国际计算机组织背景情况介绍

(Association for Computing Machinery)

ACM The First Society in Computing 是一个国际科学教育计算机组织,它致力于发展在高

级艺术、最新科学、工程技术和应用领域中的信息技术。它强调在专业领域或在社会感兴趣的领

域中培养、发展开放式的信息交换，推动高级的专业技术和通用标准的发展。

1947年，即世界第一台电子数字计算机(ENIAC)问世的第二年，ACM即成为第一个，也一直是世界

上最大的科学教育计算机组织。它的创立者和成员都是数学家和电子工程师，其中之一是约翰.迈

克利(John.Mauchly)，他是ENIAC的发明家之一。他们成立这个组织的初衷是为了计算机领域和新

兴工业的科学家和技术人员能有一个共同交换信息、经验知识和创新思想的场合。几十年的发展，

ACM的成员们为今天我们所称之为“信息时代”作出了贡献。他们所取得的成就大部分出版在ACM

印刷刊物上并获得了ACM颁发的在各种领域中的杰出贡献奖。例如：A.M.Turing奖和Grance Murr

—ay Hopper奖。

ACM组织成员今天已达到九万人之多，他们大部分是专业人员、发明家、研究员、教育家、工程师

和管理人员；三分之二以上的ACM成员，又是属于一个或多个SIGs(Special Interest Group)专

业组织成员。他们都对创造和应用信息技术有着极大的兴趣。有些最大的最领先的计算机企业和

信息工业也都是ACM的成员。

ACM就像一个伞状的组织，为散含其所有的成员提供信息，包括最新的尖端科学的发展清掘塌，从理论思想到

应用的转换，提供交换信息的机会。正象ACM建立时的初衷，它仍一直保持着它的发展“信息技

术”的目标，ACM成为一个永久的更新最新信息领域的源泉。

ACM国际大学生程序设计竞赛(英文全称:ACM International Collegiate Programming Contest（ACM-ICPC或ICPC）是由美国计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近30多年的发展，ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。赛事目前由IBM公司赞助。

竞赛的历史可以上溯到1970年，当时在美国德克萨斯A&M大学举办了首届比赛。当时的主办方是the Alpha Chapter of the UPE Computer Science Honor Society。作为一种全新的发现和培养计算机科学顶尖学生的方式答圆，竞赛很快得到美国和加拿大各大学的积极响应。1977年，在ACM计算机科学会议期间举办了首次总决赛，并演变成为目前的一年一届的多国参与的国际性比赛。迄今已经举办了29届。

最初几届比赛的参赛队伍主要来自美国和加拿大，后来逐渐发展成为一项世界范围内的竞赛。特别是自1997年IBM开始赞助赛事之后，赛事规模增长迅速。1997年，总共有来自560所大学的840支队伍参加比赛。而到了2004年，这一数字迅速增加到840所大学的4109支队伍并以每年10-20%的速度在增长。

1980年代，ACM将竞赛的总部设在位于美国德克萨斯州的贝勒大学。

在赛事的早期，冠军多为美国和加拿大的大学获得。而进入1990年代后期以来， 俄罗斯和其它一些东欧国家的大学连夺数次冠军。来自中国大陆的上海交通大学代表队则在2002年美国夏威夷的第26届和2005年上海的第29届全球总决赛上两夺冠军。这也是目前为止亚洲大学在该竞赛上取得的最好成绩。赛事的竞争格局已经由最初的北美大学一枝独秀演变成目前的亚欧对抗的局面。

ACM-ICPC以团队的形式代表各学校参赛，每队由3名队员组成。每位队员必须是在校学生，有一定的年龄限制，并且最多可以参加2次全球总决赛和5次区域选拔赛。

比赛期间，每队使用1台电脑需要在5个小时内使用C、C++、Pascal或Java中的一种编写程序解决7到10个问题。程序完成之后提交裁判运行，运行的结果会判定为正确或错误两种并及时通知参赛队。而且有趣的是每队在正确完成一题后，组织者将在其位置上升起一只代表该题颜色的气球。

最后的获胜者为正确解答题目最多且总用时最少的队伍。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次提交运行结果被判错误的话将被加罚20分钟时间，未正确解答的试题不记时。例如：A、B两队都正确完成两道题目，其中A队提交这两题的时间分别是比赛开始后1:00和2:45，B队为1:20和2: 00，但B队有一题提交了2次。这样A队的总用时为1:00+2:45=3:45而B队为1:20+2:00+0:20=3:40，所以B队以总用时少而获胜。

与其它计算机程序竞赛（例如国际信息学奥林匹克，IOI）相比，ACM-ICPC的特点在于其题量大，每队需要5小时内完成8道题目，甚至更多。另外一支队伍3名队员却只有1台电脑，使得时间显得更为紧张。因此除了扎实的专业水平，良好的团队协作和心理素质同样是获胜的关键。

美国计算机协会(Association of Computing Machinery, 简称ACM)是一个世界性的计算机从业员专业组织，创立于1947年，是世界上第一个科学性及教育性计算机学会。ACM每年都出版大量计算机科学的专门期刊，并就每项专业设有兴趣小组。兴趣小组每年亦会在全世界（但主要在美国）举办世界性讲座及会谈，以供各会员分享他们的研究成果。近年ACM积极开拓网上学习的渠道，以供会员在工余或家中提升自己的专业技能

---