一、ACM竞赛介绍及规则 / Y$ V) D) A7 R" mACM/ICPC(国际大学生程序设计竞赛)是由ACM(Association for Computing Machinery,美国计算机协会)组织的年度性竞赛,始于1970年,是全球大学生计算机程序能力竞赛活动中最有影响的一项赛事。ACM/ICPC采用赛区选拔的方式产生参加世界决赛学校的资格, 2001年,来自全球超过25个地区1141所大学的2362支队伍参加了第26届ACM/ICPC的赛区竞赛。在2002年3月,来自世界各地的约60支队伍,200多名选手参加了夏威夷总决赛的角逐。可以说,ACM国际大学生程序设计竞赛是参赛选手展示计算机才华的广阔舞台,是著名大学计算机教育成果的直接体现,是信息企业与世界顶尖计算机人才对话的最好机会。在过去十几年中,世界著名信息企业APPLE、AT&T、MICROSOFT和IBM分别担任了竞赛的赞助商。中国大陆高校从1996年开始参加ACM/ICPC亚洲预赛,前五届ACM/ICPC亚洲区选拔赛在上海设有赛区,由上海大学主办。2002年,第六届ACM/ICPC亚洲预赛将该在北京设赛区,由清华大学主办。本次竞赛将于2002年10月在清华园拉开帷幕,预计将有超过60所国内外著名大学的上百支队伍参加本次竞赛(这也是北京工业大学首次参加此项赛事)。) w9 B9 F) Z3 x1 M% u. S
@, S+ u( s' @/ w4 t! k' U P8 A) rACM竞赛规定,教练是参赛队伍所代表学校的正式教师,每支队伍最多由三名参赛队员组成,每支队伍中至少有两名参赛队员必须是未取得学士学位或同等学历的学生,取得学士学位超过两年,或进行研究生学习超过两年的学生不符合参赛队员的资格,任何参加过两次决赛的学生不得参加地区预赛或者世界决赛。 + ?8 G9 V U4 n& r* ]& ~ 4 p, {1 Q3 b1 r% l6 z* V竞赛中至少命题6题,至多命题10题,比赛时间为5个小时,参赛队员可以携带诸如书、手册、程序清单等参考资料,试题的解答提交裁判称为运行,每一次运行会被判为正确或者错误,判决结果会及时通知参赛队伍,正确解答中等数量及中等数量以上试题的队伍会根据解题数目进行排名,解题数在中等数量以下的队伍会得到确认但不会进行排名,在决定获奖和参加世界决赛的队伍时,如果多支队伍解题数量相同,则根据总用时加上惩罚时间进行排名,总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。每道试题用时将从竞赛开始到试题解答被判定为正确为止,期间每一次错误的运行将被加罚20分钟时间,未正确解答的试题不记时,地区预赛可以使用的语言包括C/C++和Java,每支队伍使用一台计算机,所有队伍使用计算机的规格配置完全相同。(竞赛具体的软件环境可能根据赞助商的变化而变)3 e4 K4 u# T9 q2 s
7 e6 z) k9 r! [1 ~) G! X二、关于竞赛的题型分析1 R! R! C8 {: K {4 v
Hal Burch通过在1999年春季的分析得出了这样的结论,竞赛的程序设计一般只有16种类型,它们分别是:! b+ S# h' G3 g, p$ W7 d" Y# S
2 t0 a: p% `1 X( @- m
Dynamic Programming (动态规划) 9 l# O, k- ]# k8 F) z4 W, e" N
Greedy (贪心算法) 6 _" W; ~# s5 f: h: Z- b) y
Complete Search (穷举搜索) 8 J. F- `1 B5 L& U3 D1 C8 z. YFlood Fill (不知该如何翻译) * p) n0 v5 n' ]; D$ MShortest Path (最短路径) 6 x/ o. S% N7 F5 D" ZRecursive Search Techniques (回溯搜索技术) ! Y5 h" R+ J# I9 \6 r3 X
Minimum Spanning Tree (最小生成树) - N3 v9 c9 E) `: Z/ S- lKnapsack (背包问题) 2 ~; x* P O, JComputational Geometry (计算几何学) 0 `" V: T0 i1 B& s# P3 j$ e ~
Network Flow (网络流) % a8 I& g/ Z4 q4 P- D
Eulerian Path (欧拉回路) ! _) L6 Y! r7 G6 W: K, K. d9 |6 K5 ^
Two-Dimensional Convex Hull (凸包问题) / B' x! k; R4 h
BigNums (大数问题) 6 v1 B+ p! T5 ]
Heuristic Search (启发式搜索) 6 T6 Y( y+ ?; V L
Approximate Search (近似搜索) 4 \" c1 a) A% ~* @: `! v
Ad Hoc Problems (杂题) + b$ [# f- z r. k/ ?4 l1 } 4 W/ h5 |; o4 \1 ]很少有人能真正掌握这其中绝大部分的方法,而对于一些包含了这些方法组合与循环的具有挑战性的综合问题,多数选手都无能为力,因为竞赛中的很多试题都需要选手当场作出分析,而不是套用固定的解题格式,这是竞赛的困难所在,也是它的魅力所在。9 S% U( D7 y9 } B- p
+ ~/ F; g* v/ R1 Q9 v三、竞赛准备 ) N4 K5 P7 ] X% L0 U8 w2 L; PACM竞赛不要求使用某一种特定的语言,所以各个队伍可以根据语言的特点和自己的特长选择,如果对语言的原理语法和特点均能做到成竹于胸、滥熟于心,在比赛的过程中就可以大大缩短调试的时间,从而获得优势。 + D6 F; o; C% }6 A7 g- A# d* R2 i2 L) K 1 s( m) U; Z# {/ ]然而编程之道就如武学之道,语言只是各门各派的武功招式,算法和数据结构则好比内功心法和武学原理。内力深厚,任何招式到了手上都能够化腐朽为神奇;掌握了武学原理,更能做到无招胜有招。选手在竞赛中最重要的素质,正体现于对算法和数据结构的掌握和理解上,通过对经典问题的分析,掌握各种算法的应用范围和数据结构的作用与具体实现,是每个选手在平时学习中的重点所在。 " S: A7 `. n5 e 1 }7 D' }" J( v/ ~8 J四、竞赛策略6 r5 Z5 j- ?# e- O* d+ _1 H
临近比赛,在实力上已经难有质的提高,这时我们不妨将注意力转移到竞赛技巧方面,做不成武学道师也学个韦小宝。在ACM竞赛中,一般来说能成功解决半数或以上题目的队伍已经是相当优秀的,解决所有问题近乎天方夜潭,也就是说无论你的实力如何,都还有很大的改进余地,这其中比较重要的就是竞赛的策略。4 S) L4 h! v2 s% a
3 M2 t8 o& `5 M. o
(1)分工的问题:) t4 b( G* I, M( H* d
团队的配合十分重要,三个队员之间的合理分工可以大大改进解题的效率,根据队员的不同特点,不同的队伍可以采用不同的分配方式,其间一些细节的处理需要三个人有很好的默契。$ n- P$ `! c1 M u( I5 i3 z5 g7 @
" f! n; w7 i9 v7 a3 d) e(2)算法的选择:4 s2 b/ l' T- g g
在所有可行的算法当中,我们选择的应该是最可行的方法,而不是最高明的方法,这是竞赛与解决问题的一个重要区别,按照熟悉的程度由高到低选择一个算法,通过计算算法的时间和空间复杂度(在必要的情况下)和特殊的测试数据找出一切使该算法不成立的理由,如果找不到就确定该算法并选用相应的数据结构。在确定思路的时候注意比较常见的思维方式分析,比如逆向的分析,对称的分析等等。; O2 s7 ]3 T9 i
o6 S9 A9 R! M% t( n
(3)程序的编写: ' a q4 v. x7 L! G5 O7 {最好首先编写输入和输出的部分,然后逐步细化,一个部分一个部分地填充调试,其间通过适量的注释来刻画程序的逻辑结构和特殊的技巧。在完成全部代码后用一般的测试数据验证代码的正确性,然后处理特殊的情况和边界问题,试图尽可能地找出错误的情况并加以改正。关于程序的优化主要考虑的是最坏情况下所用的时间是否满足要求,优化的程度以题目要求为准,足够即可,尽量避免使用指针和动态分配,在空间允许的情况下一律采用静态分配。 # d5 [% {8 @( F* r; I% M% \ D' U* N6 \' R1 d6 q# g
(4)调试中的问题: ; H" B+ n2 U3 K8 J$ ]: C+ f调试中会遇到的许多问题需要在事前有所准备并定出总体设计,当然具体的情况还要临场分析,考虑的方面包括程序中的BUG,算法的正确性和数据结构的合理性,什么时候该放弃这个问题,什么时候该返回到先前放弃的问题,是否需要做到或已经做到足够的优化等等。所有关于调试的输入输出都不要删除,将它们注释起来即可。' L0 J7 x6 h3 ~, E
7 u3 x, j7 _2 U(5)竞赛中的杂题处理8 F' Y, e' V+ @0 z: V
在竞赛中有时会出现一些新颖的题型,解决它们的算法很难归到经典的算法中去,每个这类的题都有自己鲜明的特点,对于它们根本没有一般的解法。对于这样的挑战,一个新颖的数据结构或一套特殊的循环或判断常常是必须的。解决这种问题的关键在于仔细地阅读题目的叙述,灵感经常来自于将叙述的逻辑条理整理得十分清楚之后,同样,对这类题的优化也是需要的,至少需要避免过多的循环嵌套。# ~, [0 o* n, I. I/ p% M0 f
/ S' e2 d, {- Z8 C% p
五、编程与竞赛, k: ?+ U' D t
学习编程并不是为了参加竞赛,竞赛对于多数选手的意义还是在于参与,以及在备战过程中对自己的锻炼和提高。在这一点上,ACM竞赛和其它一系列竞赛是一样的,只是它的影响力和规模大些罢了,所以笔者希望对编程有兴趣的同学都能够关注竞赛,即使不参加,通过了解竞赛中涉及的编程知识达到课内很难达到的高度,这对每个人都是有益无害的。 $ }& }( B+ Z I! Q3 ~) E0 X! ?8 y, I
C3 C1 e( ?' F2 z u
+ o' E: H2 |9 |: j% A2 c/ J7 Q一、语言是最重要的基本功 8 H4 j& {( _- M1 \ }! c& b4 H 4 i6 G( G( a9 z5 Q9 s无论侧重于什么方面,只要是通过计算机程序去最终实现的竞赛,语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA,众所周知,作为面向对象的王牌语言,JAVA在大型工程的组织与安全性方面有着自己独特的优势,但是对于信息学比赛的具体场合,JAVA则显得不那么合适,它对于输入输出流的操作相比于C++要繁杂很多,更为重要的是JAVA程序的运行速度要比C++慢10倍以上,而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽,这无疑对算法设计提出了更高的要求,是相当不利的。其实,笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维,因为对于小程序来说这不旦需要花费更多的时间去编写代码,也会降低程序的执行效率。 ! O9 c5 c6 e2 r1 G / ]9 Y" ^- U0 V接着说C和C++。许多现在参加讲座的同学还在上大一,C的基础知识刚刚学完,还没有接触过C++,其实在赛场上使用纯C的选手还是大有人在的,它们主要是看重了纯C在效率上的优势,所以这部分同学如果时间有限,并不需要急着去学习新的语言,只要提高了自己在算法设计上的造诣,纯C一样能发挥巨大的威力。 . S+ R* J5 J0 A2 ^" [( c 3 o. T/ T* r; l* X4 f而C++相对于C,在输入输出流上的封装大大方便了我们的操作,同时降低了出错的可能性,并且能够很好地实现标准流与文件流的切换,方便了调试的工作。如果有些同学比较在意这点,可以尝试C和C++的混编,毕竟仅仅学习C++的流操作还是不花什么时间的。7 B+ h) B0 K( {& q9 [: [4 y
$ s+ W9 I- \& N7 ^+ E9 Y4 X
C++的另一个支持来源于标准模版库(STL),库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度,这可以节省一些时间。但是,与此相对的,使用STL要在效率上做出一些牺牲,对于输入规模很大的题目,有时候必须放弃STL,这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法;另外,熟练和恰当地使用STL必须经过一定时间的积累,准确地了解各种操作的时间复杂度,切忌对STL中不熟悉的部分滥用,因为这其中蕴涵着许多初学者不易发现的陷阱。3 v8 i1 [ D7 @1 o
1 \* ?: h: P% Y: r4 w
通过以上的分析,我们可以看出仅就信息学竞赛而言,对语言的掌握并不要求十分全面,但是对于经常用到的部分,必须十分熟练,不允许有半点不清楚的地方,下面我举个真实的例子来说明这个道理——即使是一点很细微的语言障碍,都有可能酿成错误: + b) |8 B Y/ h 0 J2 q! O7 a$ l3 ^- n/ _在去年清华的赛区上,有一个队在做F题的时候使用了cout和printf的混合输出,由于一个带缓冲一个不带,所以输出一长就混乱了。只是因为当时 judge team中负责F题的人眼睛尖,看出答案没错只是顺序不对(答案有一页多,是所有题目中最长的一个输出),又看了看程序发现只是输出问题就给了个 Presentation error(格式错)。如果审题的人不是这样而是直接给一个 Wrong Answer,相信这个队是很难查到自己错在什么地方的。 i: v. R; @. v! } 4 w7 A9 |( [: U/ T% G: T v现在我们转入第二个方面的讨论,基础学科知识的积累。 2 x' t1 X" Q% O, I1 o0 {8 G z : j1 Y: Q. q4 ?) o2 L二、以数学为主的基础知识十分重要0 ^3 t" h- d& f
3 E, P% ~9 L3 L0 `9 @* a
虽然被定性为程序设计竞赛,但是参赛选手所遇到的问题更多的是没有解决问题的思路,而不是有了思路却死活不能实现,这就是平时积累的基础知识不够。今年 World Final的总冠军是波兰华沙大学,其成员出自于数学系而非计算机系,这就是一个鲜活的例子。竞赛中对于基础学科的涉及主要集中于数学,此外对于物理、电路等等也可能有一定应用,但是不多。因此,大一的同学也不必为自己还没学数据结构而感到不知从何入手提高,把数学捡起来吧!下面我来谈谈在竞赛中应用的数学的主要分支。 ! Q5 i! w( `1 x# w / i; H( X1 ?& W4 J; }+ u8 [1、离散数学——作为计算机学科的基础,离散数学是竞赛中涉及最多的数学分支,其重中之重又在于图论和组合数学,尤其是图论。 4 r" U; W9 J. D; E - G8 f: o0 R. I4 x图论之所以运用最多是因为它的变化最多,而且可以轻易地结合基本数据结构和许多算法的基本思想,较多用到的知识包括连通性判断、DFS和BFS,关节点和关键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流等等。虽然这部分的比重很大,但是往往也是竞赛中的难题所在,如果有初学者对于这部分的某些具体内容暂时感到力不从心,也不必着急,可以慢慢积累。 - }/ k% l0 E# g: y8 i8 A ' [1 o! R$ y e* W' O+ x竞赛中设计的组合计数问题大都需要用组合数学来解决,组合数学中的知识相比于图论要简单一些,很多知识对于小学上过奥校的同学来说已经十分熟悉,但是也有一些部分需要先对代数结构中的群论有初步了解才能进行学习。组合数学在竞赛中很少以难题的形式出现,但是如果积累不够,任何一道这方面的题目却都有可能成为难题。 7 j5 n; i# K `- F6 ]5 L ) x& }: c& N: d7 R2 _: ?. ]! C2、数论——以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决,这部分在竞赛中的比重并不大,但只要来上一道,也足以使知识不足的人冥思苦想上一阵时间。素数判断和同余最常见的是在以密码学为背景的题目中出现,在运用密码学常识确定大概的过程之后,核心算法往往要涉及数论的内容。. i) e, ]1 y3 k7 @7 E