ACM课件(lecture02)老少皆宜数学题.ppt

ACM程序设计,2020/9/1,2,第二讲,老少皆宜之数学题,2020/9/1,3,今天，,你 了吗？,AC,2020/9/1,4,开胃羹（1）,几个常用单词： 1、vertex ( vertices ) 顶点 2、polygon 多边形 3、convex 凸的 4、concave 凹的 5、segment (线)段（n）;分割（v）,2020/9/1,5,开胃羹（2）,再来几个： 1、integer 整数 2、positive 正的 3、negative (adj)负的; (n)负数 4、factorial (n)阶乘;(adj)因子的，阶乘的 5、digital (n)数字;(adj)数字的,2020/9/1,6,ACM数学题特点分析:,题意容易理解 算法相对简单（有些很难的！） 编程比较容易 ACM/ICPC入门练习的好选择 下面，分类介绍：,2020/9/1,7,从首届“舜宇”杯说起,2020/9/1,8,比赛背景,由于前一年的邀请赛很多学校没有做出一道题，所以，这次的比赛特意准备了几道简单的题目，目的就是让大多数的学校都能拿个气球回去，也好有个交待，于是有,2020/9/1,9,第一类,傻 瓜 型,2020/9/1,10,1004: Let the Balloon Rise,2020/9/1,11,Problem Description,Contest time again! How excited 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.,2020/9/1,12,Input,Input contains 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 processed.,2020/9/1,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.,2020/9/1,14,Sample Input 5 green red blue red red 3 pink orange pink 0,Sample Output red pink,2020/9/1,15,题目评述：,1. 一个让你看到后兴奋的题目,2. 只要懂点C或者C+，就可解决该问题。,2020/9/1,16,1004题目分析：,该题算法思想比较简单，就是对输入的字符串进行比较和统计。值得注意的一点是： 如果用C语言来写，要注意可能会把第一个数字后的“回车符”误认为是第一个串，字符串的比较也要用函数和循环语句。,2020/9/1,17,1008: Elevator,2020/9/1,18,Problem Description,The highest building in our city has only one elevator. A request list is made up with N positive numbers. The 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 requests 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.,2020/9/1,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 less than 100. A test case with N = 0 denotes the end of input. This test case is not to be processed.,2020/9/1,20,Output,Print the total time on a single line for each test case.,2020/9/1,21,Sample Input 1 2 3 2 3 1 0 Sample Output 17 41,2020/9/1,22,实际上，这是本次比赛最简单的一题，浙大、浙工大等当时训练水平相对较高的学校基本上10分钟之内解决该题，这也是一个没有算法的题目。 这种题目大家不会错过的,题目评述：,不要分析了吧,2020/9/1,24,第二类,基 本 型,2020/9/1,25,1009: FatMouse Trade,2020/9/1,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 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 JavaBeans he can obtain.,2020/9/1,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 are not greater than 1000.,2020/9/1,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,2020/9/1,29,Sample Input 5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1,Sample Output 13.333 31.500,2020/9/1,30,题目特点：,这个题目比前面两个题目稍难，但是属于能一眼看出解决办法的题目。只要静下心，还是比较容易解决的。,2020/9/1,31,1009算法分析：,输入（J , F 放入数组） 对数组排序（按效益，降序） 输出（按效益高低有序交易）,2020/9/1,32,第三类,技 巧 型,2020/9/1,33,小锤抠缝,先来看一个简单的题目铺垫一下：,2020/9/1,34,1021 Fibonacci Again,2020/9/1,35,Problem Description,There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n=2).,2020/9/1,36,Input Input consists of a sequence of lines, each containing an integer n. (n 1,000,000). Output Print the word yes if 3 divide evenly into F(n).Print the word no if not.,2020/9/1,37,Sample Input 0 1 2 3 4 5,Sample Output no no yes no no no,2020/9/1,38,题目分析：,能被3整除的整数的特点？,如果两个数的和能被3整除，这两个数有什么特点？,关于能否被3整除，这两个数一共有多少种组合？,2020/9/1,39,Hdoj_1021程序清单：,#include int main() long n; while(scanf(%ld, ,2020/9/1,40,回到正题大锤搞定,2020/9/1,41,1005: Number Sequence,2020/9/1,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 the value of f(n).,Problem Description,2020/9/1,43,Input The 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. Output For each test case, print the value of f(n) on a single line.,2020/9/1,44,Sample Input 1 1 3 1 2 10 0 0 0 Sample Output 2 5,2020/9/1,45,题目特点：,这个题目是一个比较典型的ACM竞赛题，尽管在真正的大赛中这个题目可能算比较简单的，但在本次比赛中，本题难度属于中等，可以说，能做出本题的队伍基本都有二等奖以上。 但如果不认真分析，有可能会掉入陷阱。,2020/9/1,46,Question:,暴力能解决问题吗？,2020/9/1,47,拒绝暴力,2020/9/1,48,题目分析：,对于这种题目，千万不能蛮干！实际上，有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。,2020/9/1,49,现在对这题有什么想法,?,2020/9/1,50,第四类,纸老虎型,2020/9/1,51,HDOJ_1071 The Area,2020/9/1,52,Sample Input 2 5.000000 5.000000 0.000000 0.000000 10.000000 0.000000 10.000000 10.000000 1.000000 1.000000 14.000000 8.222222 Sample Output 33.33 40.69,2020/9/1,53,第一眼：傻了,2020/9/1,54,再一看,2020/9/1,55,抛物线公式：y=ax2+bx+c,已知三点 -a、b、c 系数,公式已知 - 如何求面积？,会简单积分吗？,分析过程：,该你思考了,感觉怎么样？,2020/9/1,57,思考题：,1178 Heritage from father,2020/9/1,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 called 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.Harry 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 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,2020/9/1,59,Input The input will consist of some cases,each case takes a line with only one integer N(0N231).It ends with a single 0. Output 对于每个输入的N,输出一行,采用科学记数法来计算金币的总数(保留三位有效数字),2020/9/1,60,Sample Input 1 3 0 Sample Output 1.00E0 1.00E1,2020/9/1,61,要点分析：,1、暴力的复杂度是多少？ 2、哪些陷阱？ 3、关键在哪？ 4、顺利应该多长时间？,2020/9/1,62,数学公式:,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,2020/9/1,63,问题一：科学计数法的格式,不知道？ e E ,用%e : 用 %.2e,如何实现格式要求？,2020/9/1,64,解决方案,方法一： 把输出先输出到字符串，再去掉e之后的0 a=(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(n);,2020/9/1,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);,2020/9/1,66,Any question?,2020/9/1,67,课后任务：,1004、1005、1008、1009 、1060 10121014、10191021 、1061 1049、1178、1108、1030 1071、1597,2020/9/1,68,提示：关于Presentation Error 的错误,2016 输出n个数，用空格隔开 常见错误：for(i=1;i=n;i+) printf(“%d “,ai); printf(“n “); 最后一个数之后也有空格造成 Presentation Error错误,2020/9/1,69,解决办法,1、方法一 for(i=1;in;i+) printf(“%d “,ai)； printf(“%dn“,ai);,2、方法2 for(i=1;i=n;i+) printf(“%d “,ai)； if(in) printf(“n”); printf(“%d n“,ai);,2020/9/1,70,2010水仙花 #include int main() int m,n,t; int i,j; int flag; int a,b,c; flag=0;,不知道m到n有多少个水仙花数，怎么控制最后一个数后不空格？,2020/9/1,71,while(scanf(%d%d,2020/9/1,72,if(i=j) printf(%d ,i); flag=1; ,if(i=j) if(flag=1) printf( ); printf(%d,i); flag=1; ,不知道m到n有多少个水仙花数，怎么控制最后一个数后不空格？,2020/9/1,73,if(flag=0) printf(no); printf(n); return 0;,2020/9/1,74,下一讲：,递推求解,2020/9/1,75,Thank You ,