ACM(lecture-02)老少皆宜数学题PPT优秀课件

ACM程序设计程序设计杭州电子科技大学 刘春英7/3/20222第二讲第二讲老少皆宜之数学题老少皆宜之数学题7/3/20223今天，今天，你你 了吗？了吗？AC7/3/20224每周一星（每周一星（1）：）：亦纷菲幻剑亦纷菲幻剑 7/3/20225开胃羹（开胃羹（1）n几个常用单词：几个常用单词：1 1、vertex ( vertices ) vertex ( vertices ) 顶点顶点2 2、polygon polygon 多边形多边形3 3、convex convex 凸的凸的4 4、concave concave 凹的凹的5 5、segment (segment (线线) )段（段（n n）; ;分割（分割（v v）7/3/20226开胃羹（开胃羹（2）n再来几个：再来几个：1 1、integer integer 整数整数2 2、positive positive 正的正的3 3、negative (adj)negative (adj)负的负的; (n); (n)负数负数4 4、factorial (n)factorial (n)阶乘阶乘;(adj);(adj)因子的，阶乘的因子的，阶乘的5 5、digital (n)digital (n)数字数字;(adj);(adj)数字的数字的7/3/20227ACM数学题特点分析数学题特点分析:n题意容易理解题意容易理解n算法相对简单（有些很难的！）算法相对简单（有些很难的！）n编程比较容易编程比较容易nACM/ICPCACM/ICPC入门练习的好选择入门练习的好选择下面，分类介绍：下面，分类介绍：7/3/20228从首届从首届“舜宇舜宇”杯杯说起说起7/3/20229比赛背景比赛背景由于前一年的邀请赛很多学校没有做出一道由于前一年的邀请赛很多学校没有做出一道题，所以，这次的比赛特意准备了几道简单题，所以，这次的比赛特意准备了几道简单的题目，目的就是让大多数的学校都能拿个的题目，目的就是让大多数的学校都能拿个气球回去，也好有个交待，于是有气球回去，也好有个交待，于是有7/3/202210第一类第一类傻傻 瓜瓜 型型7/3/20221110041004: : Let the Balloon Rise Let the Balloon Rise7/3/202212题目评述：题目评述：1. 一个让你看到后兴奋的题目一个让你看到后兴奋的题目 2. 2. 只要懂点只要懂点C C或者或者C+C+，就可解决该问题。，就可解决该问题。7/3/20221310041004题目分析：题目分析：n该题算法思想比较简单，就是对输入的字符该题算法思想比较简单，就是对输入的字符串进行比较和统计。值得注意的一点是：串进行比较和统计。值得注意的一点是：n如果用如果用C C语言来写，要注意可能会把第一个数语言来写，要注意可能会把第一个数字后的字后的“回车符回车符”误认为是第一个串，字符误认为是第一个串，字符串的比较也要用函数和循环语句。串的比较也要用函数和循环语句。n而而C+C+则在处理字符串方面较为方便。则在处理字符串方面较为方便。7/3/20221410081008: Elevator: Elevator7/3/202215 实际上，这是本次比赛最简单的一题，浙大、实际上，这是本次比赛最简单的一题，浙大、浙工大等当时训练水平相对较高的学校基本上浙工大等当时训练水平相对较高的学校基本上1010分钟之内解决该题，这也是一个没有算法的分钟之内解决该题，这也是一个没有算法的题目。题目。 这种题目大家不会错过的这种题目大家不会错过的题目评述题目评述：7/3/202217第二类第二类基基 本本 型型7/3/2022181009: FatMouse Trade1009: FatMouse Trade7/3/202219题目特点：题目特点： 这个题目比前面两个题目稍难，但是属于能一眼看出解决办法的题目。只要静下心，还是比较容易解决的。7/3/20222010091009算法分析：算法分析：n输入（J , F 放入数组）n对数组排序（按效益，降序）n输出（按效益高低有序交易）7/3/202221第三类第三类技技 巧巧 型型7/3/202222小锤抠缝小锤抠缝先来看一个简单的题目铺垫一下：先来看一个简单的题目铺垫一下：7/3/2022231021 Fibonacci 1021 Fibonacci AgainAgain 7/3/202224题目分析：题目分析：n能被能被3 3整除的整数的特点？整除的整数的特点？还要看程序吗？还要看程序吗？n如果两个数的和能被如果两个数的和能被3 3整除，这两个数有什么整除，这两个数有什么特点？特点？n关于能否被关于能否被3 3整除，这两个数一共有多少种组整除，这两个数一共有多少种组合？合？7/3/202225Hdoj_1021Hdoj_1021程序清单：程序清单：n#includenint main()nn long n;n while(scanf(%ld,&n) != EOF)n if (n%8=2 | n%8=6)n printf(yesn);n elsen printf(non);nreturn 0;n7/3/202226回到正题回到正题大锤搞定大锤搞定7/3/202227Problem B: Number SequenceProblem B: Number Sequence7/3/202228题目特点：题目特点：这个题目是一个比较典型的这个题目是一个比较典型的ACMACM竞赛题，竞赛题，尽管在真正的大赛中这个题目可能算比较简尽管在真正的大赛中这个题目可能算比较简单的，但在本次比赛中，本题难度属于中等，单的，但在本次比赛中，本题难度属于中等，可以说，能做出本题的队伍基本都有二等奖可以说，能做出本题的队伍基本都有二等奖以上。以上。但如果不认真分析，有可能会掉入陷阱。但如果不认真分析，有可能会掉入陷阱。7/3/202229Question:Question:暴力能解决问题吗？暴力能解决问题吗？7/3/202230拒绝暴力拒绝暴力7/3/202231题目分析：题目分析：对于这种题目，千万不能蛮干！实际上，对于这种题目，千万不能蛮干！实际上，有经验的同学看到本题目的数据规模，很快就有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。能知道：这类题目有规律可循。7/3/202232现在对这题有什么想法现在对这题有什么想法?7/3/202233第四类第四类纸老虎型纸老虎型7/3/202234HDOJ_1071 The AreaHDOJ_1071 The Area 7/3/202235第一眼：傻了第一眼：傻了7/3/202236再一看再一看7/3/202237抛物线公式：抛物线公式：y=ax2+bx+cy=ax2+bx+c已知三点已知三点 - -a a、b b、c c 系数系数公式已知公式已知 - - 如何求面积？如何求面积？会简单积分吗？会简单积分吗？分析过程：分析过程：该你思该你思考了考了感觉怎感觉怎么样？么样？7/3/202239思考题：思考题：（2006/3/4 HDOJ2006/3/4 HDOJ的练习赛题目）的练习赛题目）7/3/202240要点分析：要点分析：1 1、暴力的复杂度是多少？、暴力的复杂度是多少？2 2、哪些陷阱？、哪些陷阱？3 3、关键在哪？、关键在哪？4 4、顺利应该多长时间？、顺利应该多长时间？7/3/202241数学公式数学公式: :1 1、这个大家都会：、这个大家都会：1+2+3+4+n=n(n+1)/21+2+3+4+n=n(n+1)/22 2、这个有些同学忘记了：、这个有些同学忘记了：1 1* *1+21+2* *2+32+3* *3+n3+n* *n=n(n+1)(2n+1)/6n=n(n+1)(2n+1)/63 3、合并后得到、合并后得到n(n+1)(n+2)/3n(n+1)(n+2)/37/3/202242Any question?7/3/202243课后任务：课后任务：一、一、DIYDIY在线作业在线作业(2):(2):2008ACM ProgrammingExercise（2）_Math 二、常规练习（包含以上作业）二、常规练习（包含以上作业）10041004、10051005、10081008、1009 1009 、106010601012101210141014、101910191021 1021 、1061106110491049、1066 1066 、11781178、11081108、1030 1030 10711071、159715977/3/202244下一讲：下一讲：递推求解递推求解7/3/202245Welcome to HDOJWelcome to HDOJThank Thank You You 个人观点供参考，欢迎讨论