01-acm入门

1第1章：ACM入门2第1章：ACM入门n§1ACM介绍n§2基本输入/输出n§3初学者常见问题3ACMnACM：(AssociationforComputingMachinery)n成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织…4ACM/ICPC：nACM主办的国际大学生程序设计竞赛(InternationalCollegiateProgrammingContest)，简称ACM/ICPC，自从1977年开始。其宗旨是提供一个让大学生向IT界展示自己分析问题和解决问题的能力的绝好机会，让下一代IT天才可以接触到其今后工作中将要用到的各种软件。n现在，ACM/ICPC已成为世界各国大学生中最具影响力的国际计算机赛事。（非官方）5ACM/ICPCinChinan中国大陆高校从1996年开始参加ACM国际大学生程序设计竞赛亚洲预赛。n前六届中国赛区设在上海，由上海大学承办；n2002年由清华大学和西安交通大学承办；n2003年由清华大学和中山大学承办。n2004年由北京大学和上海交通大学承办。n2005年由四川大学、北大和浙大承办。n2006年由上海大学、清华和西电承办。n2007年：北航、南航、吉大、西华6ACM/ICPCinZheJiangn每年4月，宁波市大学生程序设计大赛n每年5月，浙江省大学生程序设计大赛7如何比赛?n3人组队n可以携带诸如书、手册、程序清单等参考资料；不能携带任何可用计算机处理的软件或数据、不能携带任何类型的通讯工具；n可能收到的反馈信息包括：nCompileError;（CE）nRunTimeError;（RTE）nTimeLimitExceeded;（TLE）nWrongAnswer;（WA）nPresentationError;（PE）nAccepted;（AC）8如何排名？n首先根据解题数目进行排名。n如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。n总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。n每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。9比赛形式n1支队伍1台机器（提供打印服务）n上机编程解决问题（可带纸质资料）n实时测试，动态排名n试题n6-13题n全英文（可以带字典）n时间：持续5个小时10ACM/ICPCvs校赛nACM/ICPC:n团队合作精神n即时提交，通过所有测试数据才能得分n全英文题目，题目考察范围广n校程序设计竞赛:n个人编程能力的比拼n中文或者英文题目，考察编程基本功11ACM队队员的基本原则n基本要求n愿意花时间在ACM上n有团队合作精神n人品好n能力要求nC/C++程序设计、算法与数据结构n英语科技文献阅读n数学12宁工参赛历程131415161718开课目的n为ACM代表队培养后备人才n提高分析问题和应用计算机编程解决问题的能力n培养必要的自学能力n培养学生的协调和沟通能力n体会学习的快乐19如何入门呢?20ACM题目特点:n由于ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。n下面，分类介绍：21先看一个超级简单的题目：n=108922A+BforInput-OutputPractice(I)TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)ProblemDescriptionYourtaskistoCalculatea+b.Tooeasy?!Ofcourse!Ispeciallydesignedtheproblemforacmbeginners.Youmusthavefoundthatsomeproblemshavethesametitleswiththisone,yes,alltheseproblemsweredesignedforthesameaim.23InputTheinputwillconsistofaseriesofpairsofintegersaandb,separatedbyaspace,onepairofintegersperline.OutputForeachpairofinputintegersaandbyoushouldoutputthesumofaandbinoneline,andwithonelineofoutputforeachlineininput.SampleInput151020SampleOutput63024初学者很常见的一种写法：#includestdio.hvoidmain(){inta,b;scanf(“%d%d”,&a,&b);Printf(“%d”,a+b);}25有什么问题呢？n这就是下面需要解决的问题26§2基本输入/输出nACM的输入输出要求严格按照规定来，所以你不需要输出像“Pleaseinputthedata”这类的提示语。否则将会被判WrongAnswer。n初学者一般有个误区：如果题目包含多组测试数据，他们就会把输入的内容全部保存起来，然后再依次处理。其实程序的输入\输出是相互独立的，因此，每当处理完一组测试数据，就应当按题目要求进行相应的输出操作。而不必将所有结果储存起来一起输出。27输入_第一类：n输入不说明有多少个InputBlock,以EOF为结束标志。参见：HDOJ_1089n=108928Hdoj_1089源代码：#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)!=EOF)printf(%d\n,a+b);return0;}29本类输入解决方案：nC语法：nwhile(scanf(%d%d,&a,&b)!=EOF)n{....}nC++语法：nwhile(cinab){....}30说明（1）：nScanf函数返回值就是读出的变量个数，如：scanf(“%d%d”,&a,&b);如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是-1。nEOF是一个预定义的常量，等于-1。31输入_第二类：n输入一开始就会说有N个InputBlock,下面接着是N个InputBlock。参见：HDOJ_1090n=109032Hdoj_1090源代码：#includestdio.hintmain(){intn,i,a,b;scanf(%d,&n);for(i=0;in;i++){scanf(%d%d,&a,&b);printf(%d\n,a+b);}}33本类输入解决方案：nC语法：scanf(%d,&n);for(i=0;in;i++){....}nC++语法：cinn;for(i=0;in;i++){....}34输入_第三类：n输入不说明有多少个InputBlock,但以某个特殊输入为结束标志。n参见：HDOJ_1091n=109135Hdoj_1091源代码：#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)&&(a!=0&&b!=0))printf(%d\n,a+b);return0;}上面的程序有什么问题？36Hdoj_1091源代码（AC）#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b),a||b)printf(%d\n,a+b);return0;}37本类输入解决方案：nC语法：while(scanf(%d,&n)&&n!=0){....}nC++语法：while(cinn&&n!=0){....}38输入_第四类：n以上几种情况的组合n=1092n=1093n=109439输入_第五类：n输入是一整行的字符串的参见：HDOJ_1048n=104840本类输入解决方案：nC语法：charbuf[20];gets(buf);nC++语法：如果用stringbuf;来保存：getline(cin,buf);如果用charbuf[255];来保存：cin.getline(buf,255);41说明（5_1）：nscanf(“%s%s”,str1,str2)，在多个字符串之间用一个或多个空格分隔；n若使用gets函数，应为gets(str1);gets(str2);字符串之间用回车符作分隔。n通常情况下，接受短字符用scanf函数，接受长字符用gets函数。n而getchar函数每次只接受一个字符，经常c=getchar()这样来使用。42说明(5_2)：cin.getline的用法：ngetline是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下：istream&getline(charline[],intsize,charendchar='\n');n不用管它的返回类型，来关心它的三个参数：ncharline[]：就是一个字符数组，用户输入的内容将存入在该数组内。nintsize:最多接受几个字符？用户超过size的输入都将不被接受。ncharendchar:当用户输入endchar指定的字符时，自动结束。默认是回车符。43说明(5_2)续n结合后两个参数，getline可以方便地实现：用户最多输入指定个数的字符，如果超过，则仅指定个数的前面字符有效，如果没有超过，则用户可以通过回车来结束输入。ncharname[4];ncin.getline(name,4,'\n');n由于endchar默认已经是'\n'，所以后面那行也可以写成：ncin.getline(name,4);44输出_第一类：n一个InputBlock对应一个OutputBlock，OutputBlock之间没有空行。参见：HDOJ_1089n=108945解决方案：nC语法：{....printf(%d\n,ans);}nC++语法：{...coutansendl;}46输出_第二类：n一个InputBlock对应一个OutputBlock，每个OutputBlock之后都有空行。参见：HDOJ_1095n=1095471095源代码#includestdio.hintmain(){inta,b;while(scanf(%d%d,&a,&b)!=EOF)printf(%d\n\n,a+b);}48解决办法：nC语法：{....printf(%d\n\n,ans);}nC++语法：{...coutansendlendl;}49输出_第三类：n一个InputBlock对应一个OutputBlock，OutputBlock之间有空行。参见：HDOJ_1096n