ACM竞赛讲座.ppt

ACM大学生程序设计竞赛浅谈 ACM ICPC简介 ACM国际大学生程序设计竞赛是由美国计算机协会 ACM 主办的 一项旨在展示大学生创新能力 团队精神和在压力下编写程序 分析和解决问题能力的年度竞赛 经过近30多年的发展 ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛 一 历史竞赛的历史可以上溯到1970年 当时在美国德克萨斯A M大学举办了首届比赛 作为一种全新的发现和培养计算机科学顶尖学生的方式 竞赛很快得到美国和加拿大各大学的积极响应 1977年 举办了首次总决赛 并演变成为目前的一年一届的国际性比赛 迄今已经举办了33届 最初几届比赛的参赛队伍主要来自美国和加拿大 后来逐渐发展成为一项世界范围内的竞赛 自1997年IBM开始赞助赛事之后 赛事规模增长迅速 1997年 总共有来自560所大学的840支队伍参加比赛 2007年 来自83个国家1821所院校的6700多支参赛队参加了秋季区域预选赛 最终有100个参赛队进入了总决赛 1980年代 ACM将竞赛的总部设在位于美国德克萨斯州的贝勒大学 在赛事的早期 冠军多为美国和加拿大的大学获得 而进入1990年代后期以来 俄罗斯和其它一些东欧国家的大学连夺数次冠军 来自中国的上海交通大学代表队则在2002年美国夏威夷第26届 2005年上海举行的第29届和2010在哈尔滨第34届的全球总决赛上三夺冠军 大大推动了此竞赛在国内的开展 国内各高校都把积极组队参赛 作为培养计算机新人 展示学校计算机教学水平 提高学校知名度的重要场所 如今赛事的竞争格局已经由最初的北美大学一枝独秀演变成目前的亚欧对抗的局面 第31届ACM国际大学生程序设计大赛全球总决赛 第32届ACM国际大学生程序设计大赛全球总决赛 第34届ACM国际大学生程序设计大赛全球总决赛 冠军为上海交通大学 二 竞赛形式该项竞赛分区域预赛和国际决赛两个阶段进行 各预赛区第一名自动获得参加世界决赛的资格 世界决赛安排在每年的3 4月举行 而区域预赛安排在上一年的9月 12月在各大洲举行 ICPC比赛是以队为参赛单位的每队三人 至多有一名研究生 此外还允许有一名替补 竞赛时 每队三人仅拥有一台计算机 在五个小时内 解答5 10道题目 题目是英文的 最后解题最多的队胜出 如果做出的题数相同 则花时间少的队胜出 从何入手学习 一 语言是最重要的基本功无论侧重于什么方面 只要是通过计算机程序去最终实现的竞赛 语言都是大家要过的第一道关 比赛支持的语言包括C C 与JAVA 二 以数学为主的基础知识虽然被定性为程序设计竞赛 但参赛选手所遇到的问题更多的是没有解决问题的思路 而不是有了思路却死活不能实现 这就是平时积累的基础知识不够 竞赛中对于基础学科的涉及主要集中于数学 因此 大一的同学也不必为自己还没学数据结构而感到不知从何入手提高 把数学捡起来吧 下面来谈谈在竞赛中应用的数学的主要分支 1 离散数学2 组合数学3 数论4 计算几何5 线性代数6 概率论7 初等数学与解析几何8 高等数学 三 数据结构与算法是真正的核心数据结构掌握队列 堆栈和图的基本表达与操作是必需的 至于树 需要建树的问题有但是并不多 除此之外 排序和查找并不需要对所有方式都能很熟练的掌握 但你必须保证自己对于各种情况都有一个在时间复杂度上满足最低要求的解决方案 说到时空复杂度 竞赛时对时间的限制远远多于对空间的限制 这要求大家掌握 以空间换时间 的原则策略 算法1 算法中最基本和常用的是搜索 这里要说的是 有些初学者在学习这些搜索基本算法是不太注意剪枝 这是十分不可取的 因为所有搜索的题目给你的测试用例都不会有很大的规模 你往往察觉不出程序运行的时间问题 但是真正的测试数据一定能过滤出那些没有剪枝的算法 2 常用算法中的另一类是以 相似或相同子问题 为核心的 包括递推 递归 贪心法和动态规划 四 团队配合通过以上的介绍大家也可以看出 信息学竞赛对于知识面覆盖的非常广 想凭一己之力全部消化这些东西实在是相当困难的 这就要求我们尽可能地发挥团队协作的精神 同组成员之间的熟练配合和默契的形成需要时间 具体的情况因成员的组成不同而不同 五 练习 练习 再练习 知识的积累固然重要 但是信息学终究不是看出来的 而是练出来的 只有通过具体题目的分析和实践 才能真正掌握数学的使用和算法的应用 并在不断的练习中增加编程经验和技巧 加强团队的配合 总之 在这里光有纸上谈兵是绝对不行的 必须要通过实战来锻炼自己 大家平时可以在我们的OJ ZOJ或者POJ多多做些题目 1 尽快掌握C语言 并且自学C 2 对于算法问题 一定要花时间去理解 不要轻易放过 3 学会用google和百度来解决你所碰到的问题 4 刚刚开始的时候先多做些模拟题或者简单题目 所谓模拟题是指基本是没啥算法的题目 题目里已经清楚告诉怎么做的 大家可以多上杭电OJ去练题 关于编程 1 平时尽量使用VC或者DEVC 进行编译 2 学会DEBUG3 要养成良好的代码风格 变量名不要乱起 尽量用题目中的名词 推荐用匈牙利命名法 4 因为比赛的时候做简单题目拼的是写代码的速度 所以花点时间练习一下打字还是必要的 5 平时每份代码都要有注释 编程中应注意的问题 一 控制程序的结束1 输入要求是多组测试数据 并以 0 作为结束 例如 杭电OJ的1235 还可以测试RuntimeError 2 输入有多组测试数据 以文件末尾作为结束 例如 杭电OJ的1089 还可以测试格式错误 3 输入的测试数据组数已被给定 例如 杭电OJ的10904 输入要求是多组测试数据 并以 0 0 作为结束 例如 杭电OJ10915 在相邻的输出结果之间打印一空行 例如 杭电OJ的1096 二 字符及字符串的输入问题1 输入一行可打印字符 以回车作为结束 统计里面英文字母出现的个数 InputSampleasdAD ddf 12iunOutputSample11例程 1 cpp 2 输入数据有一行 包括两串只含英文字母的字符串并由空格隔开 输入有多组测试数据 以 end 作为结束 输出 两串字符串相同输出 same 否则输出 difference InputSampleAAAaaAAAaaOutputSamplesame例程 2 c 2 cpp 3 第一行输入一个整数N N 1000 接下来的2至N 1行 每行输入一个英文字母 输入有多组数据