ACM竞赛讲座之一-PPT课件.ppt

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