ACM竞赛简介
ACM国际大学生程序设计竞赛(ACM/ICPC:ACM International Collegiate Programming Contest)是由国际计算机界历史悠久、颇具权威性的组织ACM学会(Association for Computing Machinery,美国计算机协会)主办,是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛,其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。
竞赛的历史可以上溯到1970年,当时在美国德克萨斯A&M大学举办了首届比赛。作为一种全新的发现和培养计算机科学顶尖学生的方式,竞赛很快得到美国和加拿大各大学的积极响应。1977年,在ACM计算机科学会议期间举办了首次总决赛,并演变成为目前的一年一届的多国参与的国际性比赛。迄今已经举办了三十多届。因历届竞赛都荟萃了世界各大洲的精英,云集了计算机界的希望之星,而受到国际各知名大学的重视,并受到全世界各著名计算机公司的高度关注,成为世界各国大学生最具影响力的国际级计算机类的赛事。
最初几届比赛的参赛队伍主要来自美国和加拿大,后来逐渐发展成为一项世界范围内的竞赛。特别是自1997年IBM开始赞助赛事之后,赛事规模增长迅速。 1997年,总共有来自560所大学的840支队伍参加比赛。而到了2004年,这一数字迅速增加到840所大学的4109支队伍并以每年10~20%的速度在增长。
在赛事的早期,冠军多为美国和加拿大的大学获得。而进入上世纪九十年代后期,俄罗斯和其它一些东欧国家的大学连夺数次冠军。来自中国大陆的上海交通大学代表队则在2002年美国夏威夷第26届和2005年上海举行的第29届全球总决赛上两夺冠军。这也是目前为止亚洲大学在该竞赛上取得的最好成绩。赛事的竞争格局已经由最初的北美大学一枝独秀演变成目前的亚欧对抗的局面。
此项赛事的主办目的不仅是培养参赛选手的创造力,团队合作精神以及他们在软件程序开发过程中的创新意识,同时也是检测选手们在压力下进行开发活动的能力。可以说,ACM国际大学生程序设计竞赛是参赛选手展示计算机才华的广阔舞台,是著名大学计算机教育成果的直接体现,是信息企业与世界顶尖计算机人才对话的最好机会。该项竞赛分区域预赛和国际决赛两个阶段进行,各预赛区第一名自动获得参加世界决赛的资格,世界决赛安排在每年的3~4月举行,而区域预赛安排在上一年的9~12月在各大洲举行。
中国内地从1996年开始举办亚洲赛区预赛,前六届赛区设在上海,由上海大学主办。2002年设立了北京和西安赛区,分别由北京清华大学和西安交通大学主办。2003年,第28届ACM/ICPC亚洲赛区预赛在中国有2个赛站:北京和广州。目前,ACM/ICPC亚洲赛区预赛在中国有4个赛站,在各地轮换。
ACM竞赛规则
ACM/ICPC以团队的形式代表各学校参赛,每队由3名队员组成。每位队员必须是入校5年内的在校学生,最多可以参加2次全球总决赛和4次区域选拔赛。
竞赛中至少命题6题,至多命题10题,比赛时间为5个小时,参赛队员可以携带诸如书、手册、程序清单等参考资料,试题的解答提交裁判称为运行,每一次运行会被判为正确或者错误,判决结果会及时通知参赛队伍,根据解题数目进行排名,如果多支队伍解题数量相同,则根据总用时加上惩罚时间进行排名。每道试题用时将从竞赛开始到试题解答被判定为正确为止,期间每一次错误的运行将被加罚20分钟时间,未正确解答的试题不记时。每队在正确完成一题后,组织者将在其位置上升起一只代表该题颜色的气球。
最后的获胜者为正确解答题目最多且总用时最少的队伍。每道试题用时将从竞赛开始到试题解答被判定为正确为止,其间每一次提交运行结果被判错误的话将被加罚 20分钟时间,未正确解答的试题不记时。例如:A、B两队都正确完成两道题目,其中A队提交这两题的时间分别是比赛开始后1:00和2:45,B队为1: 20和2:00,但B队有一题提交了3次。这样A队的总用时为1:00+2:45=3:45而B队为1:20+2:00+0:40=4:00,所以A队以总用时少而获胜。
与其它计算机程序竞赛(例如国际信息学奥林匹克,IOI)相比,ACM/ICPC的特点在于其题量大,每队需要5小时内完成6~10道题目。此外,一支队伍的3名队员只有1台电脑,使得时间显得较为紧张。因此除了扎实的专业水平,良好的团队协作和心理素质同样是获胜的关键。
ACM竞赛级别
ACM程序设计竞赛可以分为4个级别:本地比赛(Local Contest)、区域赛(Area Contest)、分区赛(Regional Contest)和总决赛(Final Contest)。
ACM/ICPC竞赛考核要求
程序设计竞赛与软件工具的使用不同,它要求编程者以某种高级语言为媒介,通过构造算法去解决由现实生活中抽象出来的问题,这些问题非一般工具软件能解决。程序设计对人的能力要求是多方面的。编程者不仅要熟悉计算机语言的语法,而且还要具备:
1、扎实的数学基础和算法知识,能够对问题或者客观存在的事务及其所要解决的问题产生正确认识和理解,包括弄清楚事物属性、行为及其彼此之间的关系。
2 、娴熟的编程技术,能够把对问题及其方法的认识描述出来,最终产生一个计算机能够理解和执行的系统实现。
3 、相应的实践能力和创造能力,能够独立思考、提出质疑,拓延思路、洞悉规律,创造性地运用知识于不同的问题情景。
4 、如果真正参加竞赛,那么对心理素质的要求非常高。落后时不急不躁,领先时不盲目乐观,方能立于不败之地。同时,大学生的ACM 竞赛是三人团队共用一台机器,这对培养集体合作精神很有好处。
程序设计竞赛主要考的是数据结构、算法和数学模型,这些知识是本科阶段主要的专业基础课程,所以程序设计竞赛一定程度上可以反映出一个学校的教学水平,这也是为什么程序设计竞赛为什么规模越来越大的一个原因。正因为程序设计能比较客观地反映人的综合素质,因此,国际、国内的各种大学生和中学生信息学方面的竞赛都把程序设计作为考核内容。
在线评测系统(Online Judge)
国内:
国外:
讨论区:
武汉大学、北京大学、南京大学、上海交大、中山大学等大学BBS上的ACM/ICPC讨论区
ACM基本算法分类
一、动态规划
参考资料:
刘汝佳《算法艺术与信息学竞赛》《算法导论》
推荐题目:
简单
中等,经典TSP问题
中等,状态压缩DP
中等
中等,树形DP。可参考《算法艺术与信息学竞赛》动态规划一节的树状模型
中等,《算法艺术与信息学竞赛》中的习题
中等,《算法艺术与信息学竞赛》中的习题
中等,《算法艺术与信息学竞赛》中的习题
中等,递推
中等,需要减少冗余计算
中等,四边形不等式的简单应用
较难,状态压缩DP,《算法艺术与信息学竞赛》中有解答
较难,《算法艺术与信息学竞赛》中有解答
较难,需要配合数据结构优化(我的题目^_^)
较难,写起来比较麻烦
较难
难,树形DP
难,状态压缩DP,题目很有意思
难
非常难
二、搜索
参考资料:
刘汝佳《算法艺术与信息学竞赛》
推荐题目:
简单,深搜入门题
中等,广搜
中等,广搜
较难,广搜
难,IDA*,迭代加深搜索,需要较好的启发函数
难,可重复K最短路,A*。可参考解题报告:
难,深搜剪枝,《算法艺术与信息学竞赛》中有解答
难,《算法艺术与信息学竞赛》习题
难,深搜
较难,《算法艺术与信息学竞赛》中有解答
很难
三、常用数据结构
参考资料:
刘汝佳《算法艺术与信息学竞赛》
《算法导论》
线段树资料:
树状数组资料
关于线段树和树状数组更多相关内容可在网上搜到
后缀数组资料
推荐题目
较难,线段树应用,《算法艺术与信息学竞赛》中有解答
简单,线段树应用矩形面积并,《算法艺术与信息学竞赛》中有解答
较难,线段树应用,可参考解题报告
难,二维树状数组。
中等,线段树应用。
难,堆的应用,《算法艺术与信息学竞赛》中有解答
中等,左偏树,二项式堆或其他可合并堆的应用。
左偏树参考 http://www.nist.gov/dads/HTML/leftisttree.html
二项式堆参见《算法导论》相关章节
http://acm.pku.edu.cn/JudgeOnline/problem?id=1182
中等,并查集
中等,字典树
较难,多串匹配树
参考: http://home.ustc.edu.cn/~zhuhcheng/ACM/zzy2004.pdf
难,后缀数组
较难,最长公共子串,经典问题,后缀数组
很难,后缀数组
可参考解题报告
很难,数据结构综合运用
四、图论基础
参考资料:
刘汝佳《算法艺术与信息学竞赛》《算法导论》《网络算法与复杂性理论》谢政
推荐题目:
简单,欧拉路
中等,无向图割边
较难,无向图双连通分支
中等,最小度限制生成树,《算法艺术与信息学竞赛》中有解答
中等,最小比率生成树,《算法艺术与信息学竞赛》中有解答
简单,最短路问题
中等,差分约束系统,Bellman-Ford求解,《算法艺术与信息学竞赛》中有解答
简单,Bellman-Ford
中等,网络流
较难,网络流
中等,二部图最大匹配
较难,二部图最大匹配
中等,二部图最大权匹配
KM算法参考《网络算法与复杂性理论》
较难,二部图最大权匹配
中等,LCA(最近公共祖先)问题
参考Tarjan's LCA algorithm 《算法导论》第21章习题
较难,2-SAT问题
较难,2-SAT问题
较难,最小树形图
参考《网络算法与复杂性理论》中朱-刘算法
五、数论及组合计数基础
简单,素数判定,大数分解
参考算法导论相关章节
较难,Burnside引理
中等,解模方程组
中等,经典问题,波利亚定理
难,极好的题目,Burnside引理+模线性方程组
较难,需要数学方法,该方法在《具体数学》第七章有讲
简单,矩阵快速乘法
内蒙古自治区ACM程序设计竞赛命题预测
由于内蒙古自治区ACM程序设计竞赛属于Local级的竞赛,参赛队伍都是自治区的队伍,水平较分区赛、区域赛和世界总决赛要低。
为了让大部分参赛队都能够作出1~2道题目,所以竞赛中会有一些难度相对较低的题目。这类简单的题目可能在以下问题中出现:
(1) 大数问题:主要考虑数据的存储和表示。
(2) 字符串处理问题。
(3) 规则题:只要按照题目的要求,把所有规则都实现即可。
训练目标:(1)练习编程能力;
(2)加强组内成员间的沟通和配合;
(3)熟悉英文题目。