《ACM课件(lecture02)老少皆宜数学题.ppt》由会员分享，可在线阅读，更多相关《ACM课件(lecture02)老少皆宜数学题.ppt（75页珍藏版）》请在三一办公上搜索。
1、ACM程序设计,2023/11/7,2,第二讲,老少皆宜之数学题,2023/11/7,3,今天，,你 了吗？,AC,2023/11/7,4,开胃羹（1）,几个常用单词：1、vertex(vertices)顶点2、polygon 多边形3、convex 凸的4、concave 凹的5、segment(线)段（n）;分割（v）,2023/11/7,5,开胃羹（2）,再来几个：1、integer 整数2、positive 正的3、negative(adj)负的;(n)负数4、factorial(n)阶乘;(adj)因子的，阶乘的5、digital(n)数字;(adj)数字的,2023/11/7,6,
2、ACM数学题特点分析:,题意容易理解算法相对简单（有些很难的！）编程比较容易ACM/ICPC入门练习的好选择下面，分类介绍：,2023/11/7,7,从首届“舜宇”杯说起,2023/11/7,8,比赛背景,由于前一年的邀请赛很多学校没有做出一道题，所以，这次的比赛特意准备了几道简单的题目，目的就是让大多数的学校都能拿个气球回去，也好有个交待，于是有,2023/11/7,9,第一类,傻 瓜 型,2023/11/7,10,1004:Let the Balloon Rise,2023/11/7,11,Problem Description,Contest time again!How excited
3、 it is to see balloons floating around.But to tell you a secret,the judges favorite time is guessing the most popular problem.When the contest is over,they will count the balloons of each color and find the result.This year,they decide to leave this lovely job to you.,2023/11/7,12,Input,Input contai
4、ns multiple test cases.Each test case starts with a number N(0 N=1000)-the total number of balloons distributed.The next N lines contain one color each.The color of a balloon is a string of up to 15 lower-case letters.A test case with N=0 terminates the input and this test case is not to be processe
5、d.,2023/11/7,13,Output,For each case,print the color of balloon for the most popular problem on a single line.It is guaranteed that there is a unique solution for each test case.,2023/11/7,14,Sample Input5greenredblueredred3pinkorangepink0,Sample Outputredpink,2023/11/7,15,题目评述：,1.一个让你看到后兴奋的题目,2.只要懂
6、点C或者C+，就可解决该问题。,2023/11/7,16,1004题目分析：,该题算法思想比较简单，就是对输入的字符串进行比较和统计。值得注意的一点是：如果用C语言来写，要注意可能会把第一个数字后的“回车符”误认为是第一个串，字符串的比较也要用函数和循环语句。,2023/11/7,17,1008:Elevator,2023/11/7,18,Problem Description,The highest building in our city has only one elevator.A request list is made up with N positive numbers.The
7、numbers denote at which floors the elevator will stop,in specified order.It costs 6 seconds to move the elevator up one floor,and 4 seconds to move down one floor.The elevator will stay for 5 seconds at each stop.For a given request list,you are to compute the total time spent to fulfill the request
8、s on the list.The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.,2023/11/7,19,Input,There are multiple test cases.Each case contains a positive integer N,followed by N positive numbers.All the numbers in the input are le
9、ss than 100.A test case with N=0 denotes the end of input.This test case is not to be processed.,2023/11/7,20,Output,Print the total time on a single line for each test case.,2023/11/7,21,Sample Input1 23 2 3 10Sample Output1741,2023/11/7,22,实际上，这是本次比赛最简单的一题，浙大、浙工大等当时训练水平相对较高的学校基本上10分钟之内解决该题，这也是一个没有
10、算法的题目。这种题目大家不会错过的,题目评述：,不要分析了吧,2023/11/7,24,第二类,基 本 型,2023/11/7,25,1009:FatMouse Trade,2023/11/7,26,Problem Description,FatMouse prepared M pounds of cat food,ready to trade with the cats guarding the warehouse containing his favorite food,JavaBean.The warehouse has N rooms.The i-th room contains Ji
11、 pounds of JavaBeans and requires Fi pounds of cat food.FatMouse does not have to trade for all the JavaBeans in the room,instead,he may get Ji*a%pounds of JavaBeans if he pays Fi*a%pounds of cat food.Here a is a real number.Now he is assigning this homework to you:tell him the maximum amount of Jav
12、aBeans he can obtain.,2023/11/7,27,Input,The input consists of multiple test cases.Each test case begins with a line containing two non-negative integers M and N.Then N lines follow,each contains two non-negative integers Ji and Fi respectively.The last test case is followed by two-1s.All integers a
13、re not greater than 1000.,2023/11/7,28,Output,For each test case,print in a single line a real number accurate up to 3 decimal places,which is the maximum amount of JavaBeans that FatMouse can obtain,2023/11/7,29,Sample Input5 37 24 35 220 325 1824 1515 10-1-1,Sample Output13.333 31.500,2023/11/7,30
14、,题目特点：,这个题目比前面两个题目稍难，但是属于能一眼看出解决办法的题目。只要静下心，还是比较容易解决的。,2023/11/7,31,1009算法分析：,输入（J,F 放入数组）对数组排序（按效益，降序）输出（按效益高低有序交易）,2023/11/7,32,第三类,技 巧 型,2023/11/7,33,小锤抠缝,先来看一个简单的题目铺垫一下：,2023/11/7,34,1021 Fibonacci Again,2023/11/7,35,Problem Description,There are another kind of Fibonacci numbers:F(0)=7,F(1)=11,
15、F(n)=F(n-1)+F(n-2)(n=2).,2023/11/7,36,InputInput consists of a sequence of lines,each containing an integer n.(n 1,000,000).OutputPrint the word yes if 3 divide evenly into F(n).Print the word no if not.,2023/11/7,37,Sample Input012345,Sample Outputnonoyesnonono,2023/11/7,38,题目分析：,能被3整除的整数的特点？,如果两个数
16、的和能被3整除，这两个数有什么特点？,关于能否被3整除，这两个数一共有多少种组合？,2023/11/7,39,Hdoj_1021程序清单：,#includeint main()long n;while(scanf(%ld,2023/11/7,40,回到正题大锤搞定,2023/11/7,41,1005:Number Sequence,2023/11/7,42,A number sequence is defined as follows:f(1)=1,f(2)=1,f(n)=(A*f(n-1)+B*f(n-2)mod 7.Given A,B,and n,you are to calculate
17、the value of f(n).,Problem Description,2023/11/7,43,InputThe input consists of multiple test cases.Each test case contains 3 integers A,B and n on a single line(1=A,B=1000,1=n=100,000,000).Three zeros signal the end of input and this test case is not to be processed.OutputFor each test case,print th
18、e value of f(n)on a single line.,2023/11/7,44,Sample Input1 1 31 2 100 0 0Sample Output25,2023/11/7,45,题目特点：,这个题目是一个比较典型的ACM竞赛题，尽管在真正的大赛中这个题目可能算比较简单的，但在本次比赛中，本题难度属于中等，可以说，能做出本题的队伍基本都有二等奖以上。但如果不认真分析，有可能会掉入陷阱。,2023/11/7,46,Question:,暴力能解决问题吗？,2023/11/7,47,拒绝暴力,2023/11/7,48,题目分析：,对于这种题目，千万不能蛮干！实际上，有经验的
19、同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。,2023/11/7,49,现在对这题有什么想法,?,2023/11/7,50,第四类,纸老虎型,2023/11/7,51,HDOJ_1071 The Area,2023/11/7,52,Sample Input25.000000 5.0000000.000000 0.00000010.000000 0.00000010.000000 10.0000001.000000 1.00000014.000000 8.222222Sample Output33.3340.69,2023/11/7,53,第一眼：傻了,2023/11/7,54,
20、再一看,2023/11/7,55,抛物线公式：y=ax2+bx+c,已知三点-a、b、c 系数,公式已知-如何求面积？,会简单积分吗？,分析过程：,该你思考了,感觉怎么样？,2023/11/7,57,思考题：,1178 Heritage from father,2023/11/7,58,Famous Harry Potter,who seemd to be a normal and poor boy,is actually a wizard.Everything changed when he had his birthday of ten years old.A huge man calle
21、d Hagrid found Harry and lead him to a new world full of magic power.If youve read this story,you probably know that Harrys parents had left him a lot of gold coins.Hagrid lead Harry to Gringotts(the bank hold up by Goblins).And they stepped into the room which stored the fortune from his father.Har
22、ry was astonishing,coz there were piles of gold coins.The way of packing these coins by Goblins was really special.Only one coin was on the top,and three coins consisted an triangle were on the next lower layer.The third layer has six coins which were also consisted an triangle,and so on.On the ith
23、layer there was an triangle have i coins each edge(totally i*(i+1)/2).The whole heap seemed just like a pyramid.Goblin still knew the total num of the layers,so its up you to help Harry to figure out the sum of all the coins.,Problem Description,2023/11/7,59,InputThe input will consist of some cases
24、,each case takes a line with only one integer N(0N231).It ends with a single 0.Output对于每个输入的N,输出一行,采用科学记数法来计算金币的总数(保留三位有效数字),2023/11/7,60,Sample Input130Sample Output1.00E01.00E1,2023/11/7,61,要点分析：,1、暴力的复杂度是多少？2、哪些陷阱？3、关键在哪？4、顺利应该多长时间？,2023/11/7,62,数学公式:,1、这个大家都会：1+2+3+4+n=n(n+1)/22、这个有些同学忘记了：1*1+2*
25、2+3*3+n*n=n(n+1)(2n+1)/63、合并后得到n(n+1)(n+2)/3,2023/11/7,63,问题一：科学计数法的格式,不知道？e E,用%e:用%.2e,如何实现格式要求？,2023/11/7,64,解决方案,方法一：把输出先输出到字符串，再去掉e之后的0a=(1.0*n*n*n+3.0*n*n+2.0*n)/6.0;sprintf(str,%.2E,a);len=strlen(str);for(i=0;i=4;i+)printf(%c,stri);for(i=6;stri!=0;i+)if(i=len-1|stri!=0)printf(%c,stri);printf(
26、n);,2023/11/7,65,方法二：尾数和指数分开控制格式a=(1.0*n*n*n+3.0*n*n+2.0*n)/6.0;b=log10(a);printf(%.2lf,a/pow(10,b);printf(E%dn,b);,2023/11/7,66,Any question?,2023/11/7,67,课后任务：,1004、1005、1008、1009、106010121014、10191021、10611049、1178、1108、1030 1071、1597,2023/11/7,68,提示：关于Presentation Error 的错误,2016 输出n个数，用空格隔开常见错误：
27、for(i=1;i=n;i+)printf(“%d“,ai);printf(“n“);最后一个数之后也有空格造成Presentation Error错误,2023/11/7,69,解决办法,1、方法一for(i=1;in;i+)printf(“%d“,ai)；printf(“%dn“,ai);,2、方法2for(i=1;i=n;i+)printf(“%d“,ai)；if(in)printf(“n”);printf(“%d n“,ai);,2023/11/7,70,2010水仙花#includeint main()int m,n,t;int i,j;int flag;int a,b,c;flag=0;,不知道m到n有多少个水仙花数，怎么控制最后一个数后不空格？,2023/11/7,71,while(scanf(%d%d,2023/11/7,72,if(i=j)printf(%d,i);flag=1;,if(i=j)if(flag=1)printf();printf(%d,i);flag=1;,不知道m到n有多少个水仙花数，怎么控制最后一个数后不空格？,2023/11/7,73,if(flag=0)printf(no);printf(n);return 0;,2023/11/7,74,下一讲：,递推求解,2023/11/7,75,Thank You,
