ACM课件（lecture_03）老少皆宜数学题.ppt

《ACM课件（lecture_03）老少皆宜数学题.ppt》由会员分享，可在线阅读，更多相关《ACM课件（lecture_03）老少皆宜数学题.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、ACM ACM 程序设计程序设计计算机学院计算机学院 刘春英刘春英12/22/20221今天，今天，你 了吗？AC12/22/20222每周一星（每周一星（1）：）：06050016wuxingling12/22/20223关于期末考核的补充：关于期末考核的补充：l平时成绩30-分数组成（2（1012）其它）l期末考试70（5个题目）-分数组成（25-15-15-10-5）12/22/20224开胃羹（开胃羹（1 1）l几个常用单词：1、vertex(vertices)顶点2、polygon 多边形3、convex 凸的4、concave 凹的5、segment (线)段（n）;分割（v）12

2、/22/20225开胃羹（开胃羹（2 2）l再来几个：1、integer 整数2、positive 正的3、negative (adj)负的;(n)负数4、factorial (n)阶乘;(adj)因子的，阶乘的5、digital (n)数字;(adj)数字的12/22/20226第三讲第三讲老少皆宜之数学题12/22/20227ACMACM数学题特点分析数学题特点分析:l题意容易理解题意容易理解l算法相对简单（有些很难的！）算法相对简单（有些很难的！）l编程比较容易编程比较容易lACM/ICPC入门练习的好选择入门练习的好选择下面，分类介绍：下面，分类介绍：12/22/20228从首届从首届

3、“舜宇舜宇”杯说起杯说起12/22/20229比赛背景比赛背景由于前一年的邀请赛很多学校没有做出一道题，所以，这次的比赛特意准备了几道简单的题目，目的就是让大多数的学校都能拿个气球回去，也好有个交待，于是有12/22/202210第一类弱 智 型12/22/202211Problem A:Let the Balloon Rise12/22/202212题目评述：1.一个让你看到后兴奋的题目 2.只要懂点C或者C+，就可解决该问题。12/22/2022131004题目分析：l该题算法思想比较简单，就是对输入的字符串进行比较和统计。值得注意的一点是：l如果用C语言来写，要注意可能会把第一个数字后的

4、“回车符”误认为是第一个串，字符串的比较也要用函数和循环语句。l而C+则在处理字符串方面较为方便。12/22/202214Problem E:Elevator12/22/202215 实际上，这是本次比赛最简单的一题，浙大、浙工大等当时训练水平相对较高的学校基本上10分钟之内解决该题，这也是一个没有算法的题目。这种题目大家不会错过的题目评述：12/22/202216不要分析了吧12/22/202217第二类 基 本 型12/22/202218Problem F:Problem F:FatMouseFatMouse Trade Trade12/22/202219 题目特点：题目特点：这个题目比前

5、面两个题目稍难，但是属于能一眼看出解决办法的题目。只要静下心，还是比较容易解决的。12/22/2022201009算法分析：l输入（J,F 放入数组）l对数组排序（按效益，降序）l输出（按效益高低有序交易）12/22/202221第三类 技 巧 型12/22/202222先来看一个简单的题目铺垫一下:12/22/2022231021 Fibonacci Again1021 Fibonacci Again 12/22/202224题目分析：题目分析：l能被3整除的整数的特点？还要看程序吗？还要看程序吗？l如果两个数的和能被3整除，这两个数有什么特点？l关于能否被3整除，这两个数一共有多少种组合？

6、12/22/202225Hdoj_1021程序清单：程序清单：l#includelint main()ll long n;l while(scanf(%ld,&n)!=EOF)l if(n%8=2|n%8=6)l printf(yesn);l elsel printf(non);lreturn 0;l12/22/202226回到正题12/22/202227Problem B:Number Sequence12/22/202228题目特点：题目特点：这个题目是一个比较典型的ACM竞赛题，尽管在真正的大赛中这个题目可能算比较简单的，但在本次比赛中，本题难度属于中等，可以说，能做出本题的队伍基本都有

7、二等奖以上。但如果不认真分析，有可能会掉入陷阱。12/22/202229Question:Question:暴力能解决问题吗？暴力能解决问题吗？12/22/202230Why?12/22/202231题目分析：对于这种题目，千万不能蛮干！实际上，有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。12/22/202232现在对这题有什么想法?12/22/202233第四类 纸老虎型12/22/202234HDOJ_1071 The Area 12/22/202235第一眼：傻了12/22/202236再一看再一看 12/22/202237抛物线公式：y=ax2+bx+c已知三点

8、 -a、b、c 系数公式已知 -如何求面积？会简单积分吗？12/22/202238该你思该你思考了考了感觉怎感觉怎么样？么样？12/22/202239思考题思考题(1)：（Ural Collegiate Programming Contest 1998）http:/ Input 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.Sam

9、ple Input 6 12 Sample Output 3 12/22/202241思考：要输出的结果和哪些要输出的结果和哪些因素有关？因素有关？请发表见解。请发表见解。12/22/202242思考题思考题(2)：（3 3月月4 4日日HDOJHDOJ的练习赛题目）的练习赛题目）12/22/202243要点分析：1、暴力的复杂度是多少？2、哪些陷阱？3、关键在哪？4、顺利应该多长时间？12/22/202244数学公式:1、这个大家都会：1+2+3+4+n=n(n+1)/22、这个有些同学忘记了：1*1+2*2+3*3+n*n=n(n+1)(2n+1)/63、合并后得到n(n+1)(n+2)/

10、312/22/202245Any question?12/22/202246课后作业课后作业（简单数学题）（简单数学题）12/22/202247HDOJ作业：作业：一、一、DIY在线作业在线作业(2):ACM ProgrammingExercise（2）by LCY 二、常规练习（包含以上作业）二、常规练习（包含以上作业）1004、1005、1008、100910121014、101910211049、1060、1061、10661071、1178、1108、1030 159712/22/202248下次课内容：递推求解递推求解12/22/202249课后一定课后一定要练习！要练习！12/22/202250See you next week.Thank you!12/22/202251