《ICPC介绍》PPT课件.ppt

1,ACM/ICPC介绍及队员选拔培训机制,2,内容提要,一、ICPC介绍 二、ICPC队员选拔和培训机制 三、关于省赛的思考 四、结束语,3,内容提要,一、ICPC介绍 二、ICPC队员选拔和培训机制 三、关于省赛的思考 四、结束语,4,ACM与ICPC,ACM Association for Computer Machinery 美国计算机协会 ICPC International Collegiate Programming Contest 国际大学生程序设计竞赛 官网 /,5,ACM/ICPC 历史,1970年Texas A&M大学首次区域竞赛 1977年 区域赛总决赛（ICPC揭幕） 亚洲、美国、欧洲、太平洋地区均设有区域站点 迄今举办34届 上海交大获取3次总冠军,6,ICPC中国,中国大陆高校从1996年开始参加ACM/ICPC 前六届中国赛区设在上海，由上海大学承办； 2002年:清华大学、西安交通大学承办； 2003年:清华大学、中山大学承办。 2004年:北京大学、上海交通大学承办。 2005年:四川大学、北大和浙大承办。 2006年:上海大学、清华和西电承办。 2007年：北航、南航、吉大、西华 2008年：哈工程、北交、中科大、杭电、西南民大 2009年：哈工大、中科大、宁波理工、东华、武大,7,ICPC组队,团队赛 教练+三名正式队员+替补队员 资格 教练大学正式员工（一般教师） 队员高中毕业5年内学生（可以是研究生代表母校）,8,9,10,资格认定,教练保证参赛队员资格 每位队员最多参加2次总决赛（World Final） 每位队员每年最多参加2次区域赛 每位队员最多参加4次区域赛,11,12,ACM-ICPC比赛形式,组队参赛的形式，由三名队员组成一支队伍参赛。比赛时三名队员只使用一台电脑 比赛时间为5个小时。比赛题目为812道不等，全英文 可以带纸质资料。 选手们必须根据题目内容设计算法，并完成相应的功能要求，要么全对，要么不对，没有中间结果,13,ICPC命题及比赛时间,没有范围，很多从实际问题抽象 一般10道题左右（812） 2道左右简单题 3道左右中等偏易 3道左右中等偏难 难题 比赛连续5小时（9：3014：30）,14,ICPC排名,排名：队伍通过的题目数量多的在比赛中排名越高，题目数相同的则用时越少的排名越高 提交一次错误代码，该题提交正确后增加相应罚时,15,ICPC成绩计算,提交 队员做完一道题后将本题程序提交裁判系统，记录提交时间 判题 程序通过测试数据检验则接受，表示完成了本道题，否则记录本题提交错误一次 成绩评定 AC后：提交时间 - 比赛开始时间 = 本题用时（分钟） 罚时：提交错误次数 * 20 （分钟） 总成绩：完成题数+ ；总时间+=本题用时+罚时 不通过则不计成绩,16,返回信息,Received Accepted (AC) Presentation Error (PE) Wrong Answer (WA) Runtime Error (RE) Time Limit Exceeded (TLE) Memory Limit Exceeded (MLE) Output Limit Exceeded (OLE) Compilation Error (CE) Restricted Function (RF),17,ICPC比赛环境,OS：Linux（常用Ubuntu）， 偶见Windows Judge：PC2 /pc2/ Program：C+，C，Java,18,ICPC发展趋势,19,国内ICPC参加程序, 报名 参加网络赛获取现场赛资格 当年912月份 参加区域赛（现场赛）获取WF资格 当年912月份 参加World Final 次年4月份前后 其他邀请赛若干（上半年） 参赛费用：8001000元/队 + 差旅费,20,内容提要,一、ICPC介绍 二、ICPC队员选拔和培训机制 三、关于省赛的思考 四、结束语,21,合工大ICPC成绩,1997年参赛，未有间断 03年在中山大学首次获得铜奖 05年一枚银牌，两枚铜牌 05年北京Java challenge挑战赛第一名 06年一个金奖和两个铜奖 07年东京World Final第44名 07年1金2银1铜 08年杭州赛区铜奖 09年1银2铜,22,23,队员选拔机制,上学期针对入学新生ICPC介绍 程序设计方法与艺术课程 每年5月底或6月初举办校赛（选拔新队员） 老队员推荐新队员 毛遂自荐 选拔出正式队员,24,队员培训机制,老带新 程序设计方法与艺术课程 暑期集训 开展兴趣班，老队员为新队员授课 网络平台集训（） 自我培训，充分利用OJ,25,26,国内外OJ,北大 浙大 杭电 UVA http:/acm.uva.es/ Ural http:/acm.timus.ru Sgu http:/acm.sgu.ru/ Topcoder Google Code Jam 百度之星 ,27,ACMer 基本算法,(1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295),28,ACMer 图算法,(1)图的深度优先遍历和广度优先遍历. (2)最短路径算法poj1860,poj3259,poj1062,poj2253,poj1125,poj2240 (3)最小生成树算法 poj1789,poj2485,poj1258,poj3026 (4)拓扑排序 poj1094,29,ACMer 数据结构,(1)串 (poj1035,poj3080,poj1936) (2)排序 (poj2388,poj2299) (3)简单并查集的应用. (4)哈夫曼树(poj3253) (5)堆 (6)线段树,30,ACMer 。,算法 贪心 动态规划 数学 组合数学 计算几何 数论初步,31,学习方式,学习-练习-总结-学习-练习-总结 交流、互相学习 ACMer的博客 acm版 百度、Google（ 搜解题报告、题目 分类）,32,内容提要,一、ICPC介绍 二、ICPC队员选拔和培训机制 三、关于省赛的思考 四、结束语,33,命题-参赛-奖项设置,命题（中文命题） 各校提交候选题，组委会最后选定 选定一个学校，单独命题 聘请省外学校命题 竞赛 限制高校正式参赛队数 按ICPC规则办 省赛重新制定规则？ 奖项设置 参赛队排名，设立参赛队奖 学校排名（取该校参赛队最好成绩） 奖项内容（一、二、三等？比例设定？）,34,内容提要,一、ICPC介绍 二、ICPC队员选拔和培训机制 三、关于省赛的思考 四、结束语,35,抛砖引玉,介绍了ICPC 简介参赛概况 抛出了省赛简单思考 集思广益 讨论时间。,36,谢 谢！ 欢迎交流！,37,2010安徽省计算机程序