资源描述
,单击此处编辑母版样式,单击此处编辑幻灯片母版样式,第二层,第三层,第四层,第五层,*,*,*,本资料仅供参考,不能作为科学依据。谢谢。本资料仅供参考,不能作为科学依据。本资料仅供参考,不能作为科学依据。谢谢。本资料仅供参考!,ACM 程序设计,计算机学院 刘春英,1/51,10/6/,1,今天,,你 了吗?,AC,2/51,10/6/,2,每七天一星(1):,06050016wuxingling,3/51,10/6/,3,关于期末考评补充:,平时成绩30,-分数组成,(2(1012)其它),期末考试70(5个题目),-分数组成(25-15-15-10-5),4/51,10/6/,4,开胃羹(1),几个惯用单词:,1、vertex(vertices)顶点,2、polygon 多边形,3、convex 凸,4、concave 凹,5、segment (线)段(n);分割(v),5/51,10/6/,5,开胃羹(2),再来几个:,1、integer 整数,2、positive 正,3、negative (adj)负;(n)负数,4、factorial (n)阶乘;(adj)因子,阶乘,5、digital (n)数字;(adj)数字,6/51,10/6/,6,第三讲,老少皆宜之数学题,7/51,10/6/,7,ACM数学题特点分析:,题意轻易了解,算法相对简单(有些极难!),编程比较轻易,ACM/ICPC入门练习好选择,下面,分类介绍:,8/51,10/6/,8,从首届“舜宇”杯说起,9/51,10/6/,9,比赛背景,因为前一年邀请赛很多学校没有做出一道题,所以,这次比赛特意准备了几道简单题目,目标就是让大多数学校都能拿个气球回去,也好有个交待,于是有,10/51,10/6/,10,第一类,弱 智 型,11/51,10/6/,11,Problem A:Let the Balloon Rise,12/51,10/6/,12,题目评述:,1.一个让你看到后兴奋题目,2.只要懂点C或者C+,就可处理该问题。,13/51,10/6/,13,1004题目分析:,该题算法思想比较简单,就是对输入字符串进行比较和统计。值得注意一点是:,假如用C语言来写,要注意可能会把第一个数字后“回车符”误认为是第一个串,字符串比较也要用函数和循环语句。,而C+则在处理字符串方面较为方便。,14/51,10/6/,14,Problem E:Elevator,15/51,10/6/,15,实际上,这是此次比赛最简单一题,浙大、浙工大等当初训练水平相对较高学校基本上10分钟之内处理该题,这也是一个没有算法题目。,这种题目大家不会错过,题目评述:,16/51,10/6/,16,不要分析了吧,17/51,10/6/,17,第二类 基 本 型,18/51,10/6/,18,Problem F:FatMouse Trade,19/51,10/6/,19,题目特点:,这个题目比前面两个题目稍难,不过属于能一眼看出处理方法题目。只要静下心,还是比较轻易处理。,20/51,10/6/,20,1009算法分析:,输入(J,F 放入数组),对数组排序(按效益,降序),输出(按效益高低有序交易),21/51,10/6/,21,第三类 技 巧 型,22/51,10/6/,22,先来看一个简单题目铺垫一下:,23/51,10/6/,23,1021 Fibonacci Again,24/51,10/6/,24,题目分析:,能被3整除整数特点?,还要看程序吗?,假如两个数和能被3整除,这两个数有什么特点?,关于能否被3整除,这两个数一共有多少种组合?,25/51,10/6/,25,Hdoj_1021程序清单:,#include,int main(),long n;,while(scanf(%ld,&n)!=EOF),if(n%8=2|n%8=6),printf(yesn);,else,printf(non);,return 0;,26/51,10/6/,26,回到正题,27/51,10/6/,27,Problem B:Number Sequence,28/51,10/6/,28,题目特点:,这个题目是一个比较经典ACM竞赛题,尽管在真正大赛中这个题目可能算比较简单,但在此次比赛中,本题难度属于中等,能够说,能做出本题队伍基本都有二等奖以上。,但假如不认真分析,有可能会掉入陷阱。,29/51,10/6/,29,Question:,暴力能处理问题吗?,30/51,10/6/,30,Why?,31/51,10/6/,31,题目分析:,对于这种题目,千万不能蛮干!实际上,有经验同学看到本题目标数据规模,很快就能知道:这类题目有规律可循。,32/51,10/6/,32,现在对这题有什么想法,?,33/51,10/6/,33,第四类 纸老虎型,34/51,10/6/,34,HDOJ_1071 The Area,35/51,10/6/,35,第一眼:傻了,36/51,10/6/,36,再一看,37/51,10/6/,37,抛物线公式:y=ax2+bx+c,已知三点 -a、b、c 系数,公式已知 -怎样求面积?,会简单积分吗?,38/51,10/6/,38,该你思索了,感觉怎么样?,39/51,10/6/,39,思索题(1):,(Ural Collegiate Programming Contest 1998),contains two integer numbers M and N in the range from 1 to 1000000000 separated with space(s).,Output,Output should contain the length of the shortest route.,Sample Input,6 12,Sample Output,3,41/51,10/6/,41,思索:,要输出结果和哪些原因相关?,请发表看法。,42/51,10/6/,42,思索题(2):,(3月4日HDOJ练习赛题目),43/51,10/6/,43,关键点分析:,1、暴力复杂度是多少?,2、哪些陷阱?,3、关键在哪?,4、顺利应该多长时间?,44/51,10/6/,44,数学公式:,1、这个大家都会:1+2+3+4+n=n(n+1)/2,2、这个有些同学忘记了:,1*1+2*2+3*3+n*n=n(n+1)(2n+1)/6,3、合并后得到n(n+1)(n+2)/3,45/51,10/6/,45,Any question?,46/51,10/6/,46,课后作业(简单数学题),47/51,10/6/,47,HDOJ作业:,一、DIY在线作业(2):,ACM ProgrammingExercise(2)by LCY,二、常规练习(包含以上作业),1004、1005、1008、1009,10121014、10191021,1049、1060、1061、1066,1071、1178、1108、1030,1597,48/51,10/6/,48,下次课内容:,递推求解,49/51,10/6/,49,课后一定要练习!,50/51,10/6/,50,See you next week.,Thank you!,51/51,10/6/,51,
展开阅读全文