ACM竞赛讲座之一1.ppt

ACM竞赛的培训（之一）,廖雪峰温州大学瓯江学院,ACM的介绍,ACM/ICPC（国际大学生程序设计竞赛）是由ACM(AssociationforComputingMachinery，美国计算机协会)组织的年度性竞赛，始于1970年，是全球大学生计算机程序能力竞赛活动中最有影响的一项赛事。,ACM/ICPC是参赛选手展示计算机才华的广阔舞台，是著名大学计算机教育成果的直接体现，是信息企业与世界顶尖计算机人才对话的最好机会。在过去十几年中，世界著名信息企业APPLE、ATRunTimeError;TimeLimitExceeded;WrongAnswer;PresentationErrorAccepted,首先根据解题数目进行排名。如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。,如何排名？,比赛形式,1支队伍1台机器（提供打印服务）上机编程解决问题（可带纸质资料）实时测试，动态排名试题8-10题全英文（可以带字典）时间：持续5个小时,ACM.vs.校程序设计竞赛,ACM竞赛团队合作精神即时提交，通过所有数据才能得分全英文题目，题目考察范围广校程序设计竞赛个人编程能力的比拼中文或英文（以后全英文），考察编程基本功,ACM队队员的基本原则,基本要求人品好愿意花时间在这项赛事上有团队合作精神能力要求程序设计英语科技文献阅读数学,杭电信息工程学院ACM,参赛历史20052人2人银牌20062队1铜20072队1银20086队2银1铜（省内排名？）2009？,2008省赛排名情况,金奖银奖113041浙江大学：4812杭州电子：268（另：4铜）浙江工大：246（另：2铜）宁波理工：224（另：2铜）宁波大学：112浙江师大：044杭电信息：022温州大学：011浙江理工：011工大之江：011,竞赛规则,竞赛中至少命题6题，至多命题10题比赛时间为5个小时参赛队员可以携带诸如书、手册、程序清单等参考资料试题的解答提交裁判称为运行，每一次运行会被判为正确或者错误，判决结果会及时通知参赛队伍使用的语言包括C/C+，每支队伍使用一台计算机,竞赛环境,竞赛时间：2012年5月？日12:0017:00。开幕式、熟悉场地时间：2009年5月？日8:00。闭幕式时间：2012年5月？日19:00。竞赛地点：浙江大学紫金港校区计算中心机房。竞赛语言包括C+和C。每支队伍使用一台计算机，所有队伍使用计算机的规格配置完全相同。,开课目的,为瓯江ACM代表队培养后备人才提高分析问题和应用计算机编程解决问题的能力培养必要的自学能力培养学生的协调和沟通能力体会学习的快乐,练习环境,浙江大学ACM网站现提供一千余道练习题目以及在线自动判题系统可在该网站注册后进行练习例如题号1001A+BProblem,详细内容.,如何入门呢?,ACM题目特点:,由于ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。下面，分类介绍：,先看一个超级简单的题目：,初学者很常见的一种写法：,#includevoidmain()inta,b;scanf(“%d%d”,有什么问题呢？,这就是下一次需要解决的问题,Elevator2108,#includestdio.hintmain()intsum,n=1,next,now;scanf(%d,涉及什么知识？,直接相关：C程序设计、离散数学、数据结构、算法分析；重要基础：英语、高等数学（数学分析）、线性代数、操作系统、编译原理、人工智能；,C程序设计,输入输出格式程序结构运算符和表达式,基本控制语句,A,B,P,A,B,A,P,顺序,选择,循环,基本控制语句,赋值语句,函数调用语句,复合语句,实现顺序结构的语句,实现选择结构的语句,实现循环结构的语句,if语句,switch语句,while语句,do-while语句,for语句,基本控制语句_选择,if(P)A;elseB;,P,A,B,基本控制语句_选择,if(P)A;,A,P,基本控制语句_选择,if(P1)A;elseif(P2)B;elseC,B,A,P1,P2,C,基本控制语句_选择,Switch(exp)case值1：语句1；break;case值2：语句1；break;default:语句n+1;,exp,语句n+1,语句2,语句1,基本控制语句_循环,while(P)A;,A,P,基本控制语句_循环,doA;while(P);,A,P,基本控制语句_循环,for(B;P;C)A;,B,P,C,A,数据结构,线性表队列、堆栈排序、查找（至少掌握1种）,详细内容.,算法的复杂性,在NumberSequence中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)mod7.不可行的方法：intf100000000for(i=0;i100000000;i+),强化训练计划,短期的突击,详细计划,4月1-15日：C语言知识复习、浙大ACM的自动判卷环境、数据结构4月16-30日：自己的强化训练（至少30题提交成功）、讲座5月19-24日：经验总结（程序格式、编程方法）、选拔参赛,5月？日,竞赛与自我发展,学习编程并不是为了参加竞赛，竞赛对于多数选手的意义还是在于参与，以及在备战过程中对自己的锻炼和提高。ACM竞赛和其它一系列竞赛是一样的，只是它的影响力和规模大些罢了，所以希望对编程有兴趣的同学都能够关注竞赛，即使不参加，通过了解竞赛中涉及的编程知识达到课内很难达到的高度，这对每个人都是有益无害的。,瓯江学院学科竞赛颁奖,常见问题：,1、需要什么基础？(C