南邮ACM算法与数据结构设计(2010-2011-2第1讲)

陈老师(南邮ACM竞赛教练)

南京邮电大学计算机学院联系方式 电话：138-139-30027 电邮：acm@http://www.77cn.com.cn

ACM算法与数据结构设计班 级 ：仙林校区ACM选修班 上课地点和时间

理论：教2-402:星期3 (18:30开始)实践：(仙林)计算中心

第1讲: ACM/ICPC概述

找寻世界上最聪明的人

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.1 ACM/ICPC历史回顾 大陆高校1996年开始参加亚洲预赛，如清

华大学、北京大学、上海交通大学等，每年 一般有队伍参加世界决赛。 在赛事的早期，冠军多为美国和加拿大的

大学获得。近年来，俄罗斯和其它一些东欧 国家的大学连夺数次冠军。上海交通大学在 2002、2005、2010年全球总决赛上三夺冠军。

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.1 ACM/ICPC历史回顾

自1997年IBM开始赞助赛事之后，赛事规 模增长迅速。

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.1 ACM/ICPC历史回顾

自1977年以来，历年全球总决赛的冠军年份 总决赛地点 冠军大学 国家

19771978 1979

美国亚特兰大美国底特律 美国代顿

密歇根州立大学麻省理工学院 华盛顿大学圣路易斯分校

美国美国 美国

1980 19811982 1983

美国堪萨斯城 美国圣路易斯美国印第安纳波利斯 美国墨尔本

华盛顿大学圣路易斯分校 密苏里-罗拉大学贝勒大学 内布拉斯加大学

美国 美国美国 美国

1984

美国费城

约翰霍普金斯大学

美国

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.1 ACM/ICPC历史回顾

自1977年以来，历年全球总决赛的冠军年份 总决赛地点 冠军大学 国家

19851986 1987

美国新奥尔良美国辛辛那提 美国圣路易斯

斯坦福大学加州理工学院 斯坦福大学

美国美国 美国

1988 19891990 1991

美国亚特兰大 美国路易斯维尔美国华盛顿 美国圣安东尼奥

加州理工学院 加州大学洛杉矶分校奥塔哥大学 斯坦福大学

美国 美国新西兰 美国

1992

美国堪萨斯城

墨尔本大学

澳大利亚

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.1 ACM/ICPC历史回顾年份1993 1994 1995 1996 1997 1998 1999 2000 2001

总决赛地点美国印第安纳波利斯 美国菲尼克斯 美国纳什维尔 美国费城 美国圣何塞 美国亚特兰大 荷兰埃因霍温 美国奥兰多 加拿大温哥华 哈佛大学 滑铁卢大学

冠军大学

国家美国 美国 德国 美国 美国 捷克 加拿大 俄罗斯 俄罗斯

阿尔伯特-爱因斯坦大学 加州大学伯克利分校 哈维玛德大学 查尔斯大学 滑铁卢大学 圣彼得堡州立大学 圣彼得堡州立大学

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.1 ACM/ICPC历史回顾年份 总决赛地点 上海交通大学 华沙大学 圣彼得堡国立精密机械和光学学院 上海交通大学 萨拉托夫州立大学 华沙大

学 圣彼得堡国立信息技术、机械与光学大学 圣彼得堡国立信息技术、机械与光学大学 上海交通大学 冠军大学 国家 中国 波兰 俄罗斯 中国 俄罗斯 波兰 俄罗斯 俄罗斯 中国 2002 美国夏威夷 2003 美国洛杉矶 2004 捷克布拉格 2005 中国上海 2006 美国德克萨斯州 2007 日本东京 2008 加拿大班夫 2009 瑞典斯德哥尔摩 2010 中国哈尔滨

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.1 ACM/ICPC历史回顾

自1977年以来，历年全球总决赛的冠军Top institutions Wins3 3 3 2 2 2 2 2

InstitutionShanghai Jiao Tong University St. Petersburg State University of IT, Mechanics and Optics Stanford University California Institute of Technology Saint Petersburg State University University of Warsaw University of Waterloo Washington University in St. Louis

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.1 ACM/ICPC历史回顾

自1977年以来，历年全球总决赛的冠军By country Contests17 6 3 2 2 1 1 1 1 United States Russia China Canada Poland Australia Czech Republic Germany New Zealand

Country

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.2 ACM/ICPC竞赛制度

ACM/ICPC 赛程

两个阶段： 1. 区 域 预 赛 2. 国际决赛

区域预赛(Regional Contests)

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.2 ACM/ICPC竞赛制度

ACM/ICPC 赛程

两个阶段： 1. 区 域 预 赛 2. 国际决赛

国际决赛(World Finals)

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.2 ACM/ICPC竞赛制度

ACM/ICPC 现场赛制1. 3人组队比赛，在连续5小时内，使用1台计算机 (提供打印服务),使用C、C++或Java编程挑战811道赛题，解决问题最多者获胜。解决问题一样多， 则耗时最少者获胜。

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.2 ACM/ICPC竞赛制度

ACM/ICPC 现场赛制2. 程序完成之后通过网络提交到服务器，主要由服务 器自动编译运行并判别运行结果是否正确，有时会 有 Special Judge 人工判别。

第1讲: ACM/ICPC概述1.1 Models and Modeling 1.2 ACM/ICPC竞赛制度

ACM/ICPC 现场赛制3. 程序提交后，可能得到以下结果： (1)Accepted (AC):正确 (2)Compile Error (CE) :编译错 (3)Runtime Error (RE):运行时出错 (4)Wrong Answer (WA):结果错 (5)Presentation Error (PE) :格式错 (6)Time Limit Exceed (TLE) :运行超时， (7)Memory Limit Exceed (MLE) :超出空间限制 等等 结果会及时通知参赛队。