ACM竞赛讲座之一

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二层,第三层,第四层,第五层,*,ACM竞赛的培训,（之一）,1,ACM的介绍,ACM/ICPC,（国际大学生程序设计竞赛）是由ACM(Association for Computing Machinery，美国计算机协会)组织的年度性竞赛，始于1970年，是,全球,大学生计算机程序能力竞赛活动中,最有影响,的一项赛事。,2,ACM/ICPC,是参赛选手展示计算机才华的广阔舞台，是著名大学计算机教育成果的直接体现，是,信息企业与世界顶尖计算机人才,对话的最好机会。,在过去十几年中，世界著名信息企业APPLE、AT&T、MICROSOFT和IBM分别担任了竞赛的赞助商。,中国大陆,高校从,1996年,开始参加ACM/ICPC亚洲预赛,浙江省较早参与高校有浙江大学、浙江工业大学,3,ACM/ICPC in China,中国大陆高校从1996年开始参加ACM/ICPC,前六届中国赛区设在上海，由上海大学承办；,2002年由清华大学和西安交通大学承办；,2003年由清华大学和中山大学承办。,2004年由北京大学和上海交通大学承办。,2005年由四川大学、北大和浙大承办。,2006年由上海大学、清华和西电承办。,2007年：北航、南航、吉大、西华,2008年：哈工程、北交、合肥、,杭电,、西南民大,4,ACM in wzu,2003年9月，第一次参加此类比赛（浙大邀请赛）,20042008，每年5月,浙江省第15届大学生程序设计竞赛,2008年4月，瓯江首届邀请赛,5,2008浙江省第五届大学生程序设计竞赛 （回顾）,全省72所本专科院校,300支队伍参赛,最强的阵容,历届规模最大、水平最高的程序设计竞赛,详细内容.,6,浙江省第五届大学生程序设计竞赛本科组三等奖,胡盛迭、洪智妍、张慧同学,7,预期赛事（今后每年）,3-4月，举行校内大赛（暨选拔赛）,5月，参加浙江省大学生程序设计大赛,另外，每学期适当的练习赛,8,如何比赛?,3人组队,可以携带诸如书、手册、 程序清单等参考资料；不能携带任何可用计算机处理的软件或数据、不能携带任何类型的通讯工具；,可能收到的反馈信息包括：,Compile Error,;,Run Time Error;,Time Limit Exceeded;,Wrong Answer,;,Presentation Error,Accepted,9,首先根据解题数目进行排名。,如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。,总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。,每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚,20,分钟时间，未正确解答的试题不记时。,如何排名？,10,比赛形式,1支队伍1台机器（提供打印服务）,上机编程解决问题（可带纸质资料）,实时测试，动态排名,试题,8-10题,全英文（可以带字典）,时间：持续5个小时,11,ACM .vs. 校程序设计竞赛,ACM竞赛,团队合作精神,即时提交，通过所有数据才能得分,全英文题目，题目考察范围广,校程序设计竞赛,个人编程能力的比拼,中文或英文（以后全英文），考察编程基本功,12,ACM队队员的基本原则,基本要求,人品好,愿意花时间在这项赛事上,有团队合作精神,能力要求,程序设计,英语科技文献阅读,数学,13,杭电信息工程学院ACM,参赛历史,2005 2人 2人银牌,2006 2队 1铜,2007 2队 1银,2008 6队 2银1铜（省内排名？）,2009 ？ ？,14,2008,省赛排名情况,金奖银奖113041,浙江大学：4812,杭州电子：268（另：4铜）,浙江工大：246（另：2铜）,宁波理工：224（另：2铜）,宁波大学：112,浙江师大：044,杭电信息：022,温州大学：011,浙江理工：011,工大之江：011,15,竞赛规则,竞赛中至少命题6题，至多命题10题,比赛时间为5个小时,参赛队员可以携带诸如书、手册、程序清单等参考资料,试题的解答提交裁判称为运行，每一次运行会被判为正确或者错误，判决结果会及时通知参赛队伍,使用的语言包括C/C+，每支队伍使用一台计算机,16,竞赛环境,竞赛时间：2012年5月？日 12:0017:00。,开幕式、熟悉场地时间：2009年5月？日8:00。,闭幕式时间：2012年5月？日19:00。,竞赛地点：浙江大学紫金港校区计算中心机房。,竞赛语言包括C+ 和 C。,每支队伍使用一台计算机，所有队伍使用计算机的规格配置完全相同。,17,18,开课目的,为瓯江ACM代表队培养后备人才,提高分析问题和应用计算机编程解决问题的能力,培养必要的自学能力,培养学生的协调和沟通能力,体会学习的快乐,19,练习环境,浙江大学ACM网站现提供一千余道练习题目以及在线自动判题系统,可在该网站注册后进行练习,例如 题号1001,A + B Problem,详细内容.,20,如何入门呢?,21,ACM题目特点:,由于ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。,下面，分类介绍：,22,先看一个超级简单的题目：,Sample input:,1 5,10 20,Sample output:,6,30,23,初学者很常见的一种写法：,#include,void main(),int a,b;,scanf(“%d %d”,Printf(“%d”,a+b);,24,有什么问题呢？,这就是下一次需要解决的问题,25,Elevator 2108,#include stdio.h,int main(), int sum,n=1,next,now;,scanf(%d,while(n), scanf(%d,sum=5*n;,for(now=0;n0;n-), scanf(%d,sum+=(next-now)*(next-now)0)?6:-4);,now=next;,printf(%dn,sum);,26,涉及什么知识,？,直接相关：,C,程序设计,、离散数学、,数据结构,、算法分析；,重要基础：,英语,、,高等数学,（数学分析）、线性代数、操作系统、编译原理、人工智能；,27,C,程序设计,输入输出格式,程序结构,运算符和表达式,28,基本控制语句,A,B,P,A,B,A,P,顺序,选择,循环,29,基本控制语句,赋值语句,函数调用语句,复合语句,实现顺序结构的语句,实现选择结构的语句,实现循环结构的语句,if,语句,switch,语句,while,语句,do-while,语句,for,语句,30,基本控制语句_选择,if( P ),A;,else,B;,P,A,B,31,基本控制语句_选择,if( P ),A;,A,P,32,基本控制语句_选择,if( P1 ),A;,else if ( P2 ),B;,else,C,B,A,P1,P2,C,33,基本控制语句_选择,Switch (exp ),case 值1：,语句1；,break;,case 值2：,语句1；,break;,default:,语句n+1;,exp,语句n+1,语句2,语句1,34,基本控制语句_循环,while( P ),A;,A,P,35,基本控制语句_循环,do,A;,while( P );,A,P,36,基本控制语句_循环,for( B; P; C),A;,B,P,C,A,37,数据结构,线性表,队列、堆栈,排序、查找（至少掌握1种）,详细内容.,38,算法的复杂性,在Number Sequence中,1=A,B=1000,1=n=100,000,000),f(1) = 1, f(2) = 1;,f(n) =(A*f(n-1)+B*f(n-2) mod 7.,不可行的方法：,int f100000000,for(i=0;i100000000;i+),39,强化训练计划,短期的突击,详细计划,4月1-15日： C语言知识复习、浙大ACM的自动判卷环境、数据结构,4月16-30日：自己的强化训练（至少30题提交成功）、讲座,5月19-24日：经验总结（程序格式、编程方法）、选拔参赛,4月,1日,15日,16日,30日,5月1日,15日,基础回顾和环境入门,强化训练与培训,技巧方法,5月？日,40,竞赛与自我发展,学习编程并不是为了参加竞赛，竞赛对于多数选手的意义还是在于参与，以及在,备战过程,中对自己的,锻炼,和,提高,。,ACM竞赛和其它一系列竞赛是一样的，只是它的,影响力,和,规模大,些罢了，所以希望对编程有,兴趣,的同学都能够关注竞赛，即使不参加，通过了解竞赛中涉及的编程知识,达到课内很难达到的高度,，这对每个人都是有益无害的。,41,瓯江学院学科竞赛颁奖,42,常见问题：,1、需要什么基础？( C/C+ ),4 、可以退课吗? ( Of course! ),3 、如何加入集训队?,2、英语不好怎么办？(问题不大),43,课后任务：,1、熟悉,2、完成在线练习：,基本输入输出练习,3、学有余力，可以尝试下面题目:,1016-1018、1013、1061,1170、2000-2043,44,