《ACM課件(lecture02)老少皆宜數(shù)學(xué)題.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《ACM課件(lecture02)老少皆宜數(shù)學(xué)題.ppt（75頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、ACM程序設(shè)計(jì),2020/9/1,2,第二講,老少皆宜之?dāng)?shù)學(xué)題,2020/9/1,3,今天，,你 了嗎？,AC,2020/9/1,4,開胃羹（1）,幾個(gè)常用單詞： 1、vertex ( vertices ) 頂點(diǎn) 2、polygon 多邊形 3、convex 凸的 4、concave 凹的 5、segment (線)段（n）;分割（v）,2020/9/1,5,開胃羹（2）,再來幾個(gè)： 1、integer 整數(shù) 2、positive 正的 3、negative (adj)負(fù)的; (n)負(fù)數(shù) 4、factorial (n)階乘;(adj)因子的，階乘的 5、digital (n)數(shù)字;(adj)
2、數(shù)字的,2020/9/1,6,ACM數(shù)學(xué)題特點(diǎn)分析:,題意容易理解 算法相對(duì)簡單（有些很難的?。。?編程比較容易 ACM/ICPC入門練習(xí)的好選擇 下面，分類介紹：,2020/9/1,7,從首屆“舜宇”杯說起,2020/9/1,8,比賽背景,由于前一年的邀請(qǐng)賽很多學(xué)校沒有做出一道題，所以，這次的比賽特意準(zhǔn)備了幾道簡單的題目，目的就是讓大多數(shù)的學(xué)校都能拿個(gè)氣球回去，也好有個(gè)交待，于是有,,2020/9/1,9,第一類,傻 瓜 型,2020/9/1,10,1004: Let the Balloon Rise,2020/9/1,11,Problem Description,Contest time
3、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
4、,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
5、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
6、 red pink,2020/9/1,15,題目評(píng)述：,1. 一個(gè)讓你看到后興奮的題目,2. 只要懂點(diǎn)C或者C++，就可解決該問題。,2020/9/1,16,1004題目分析：,該題算法思想比較簡單，就是對(duì)輸入的字符串進(jìn)行比較和統(tǒng)計(jì)。值得注意的一點(diǎn)是： 如果用C語言來寫，要注意可能會(huì)把第一個(gè)數(shù)字后的“回車符”誤認(rèn)為是第一個(gè)串，字符串的比較也要用函數(shù)和循環(huán)語句。,2020/9/1,17,1008: Elevator,2020/9/1,18,Problem Description,The highest building in our city has only one elevator. A r
7、equest 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 a
8、re 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, followe
9、d 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,202
10、0/9/1,22,實(shí)際上，這是本次比賽最簡單的一題，浙大、浙工大等當(dāng)時(shí)訓(xùn)練水平相對(duì)較高的學(xué)校基本上10分鐘之內(nèi)解決該題，這也是一個(gè)沒有算法的題目。 這種題目大家不會(huì)錯(cuò)過的,題目評(píng)述：,不要分析了吧,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 favori
11、te 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 nu
12、mber. 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 int
13、egers 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,
14、,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,題目特點(diǎn)：,這個(gè)題目比前面兩個(gè)題目稍難，但是屬于能一眼看出解決辦法的題目。只要靜下心，還是比較容易解決的。,2020/9/1,31,1009算法分析：,輸入（J , F 放入數(shù)組） 對(duì)數(shù)組排序（按效益，降序） 輸出（按效益高低有序交易）,2020/9/1,32,第三類,技 巧 型,2020/9/1,33,小錘摳縫,先來看一個(gè)簡單的題目鋪墊一下：,2020/9/1,34,1021 Fibonacci
15、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 t
16、he 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整除的整數(shù)的特點(diǎn)？,如果兩個(gè)數(shù)的和能被3整除，這兩個(gè)數(shù)有什么特點(diǎn)？,關(guān)于能否被3整除，這兩個(gè)數(shù)一共有多少種組合？,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,20
17、20/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 o
18、n 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,題目特點(diǎn)：,這個(gè)題目是一個(gè)比較典型的
19、ACM競賽題，盡管在真正的大賽中這個(gè)題目可能算比較簡單的，但在本次比賽中，本題難度屬于中等，可以說，能做出本題的隊(duì)伍基本都有二等獎(jiǎng)以上。 但如果不認(rèn)真分析，有可能會(huì)掉入陷阱。,2020/9/1,46,Question:,暴力能解決問題嗎？,2020/9/1,47,拒絕暴力,2020/9/1,48,題目分析：,對(duì)于這種題目，千萬不能蠻干！實(shí)際上，有經(jīng)驗(yàn)的同學(xué)看到本題目的數(shù)據(jù)規(guī)模，很快就能知道：這類題目有規(guī)律可循。,2020/9/1,49,現(xiàn)在對(duì)這題有什么想法,???,2020/9/1,50,第四類,紙老虎型,2020/9/1,51,HDOJ_1071 The Area,2020/9/1,52,S
20、ample 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,已知三點(diǎn) -a、b、c 系數(shù),公式已知 - 如何求面積？,會(huì)簡單積分嗎？,分析過程：,該你思考了,感覺怎么樣？,2020/9/1,57,思考題：,1178 Herit
21、age 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 tha
22、t 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 speci
23、al.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.
24、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(0
25、算金幣的總數(shù)(保留三位有效數(shù)字),2020/9/1,60,Sample Input 1 3 0 Sample Output 1.00E0 1.00E1,2020/9/1,61,要點(diǎn)分析：,1、暴力的復(fù)雜度是多少？ 2、哪些陷阱？ 3、關(guān)鍵在哪？ 4、順利應(yīng)該多長時(shí)間？,2020/9/1,62,數(shù)學(xué)公式:,1、這個(gè)大家都會(huì)：1+2+3+4+n=n(n+1)/2 2、這個(gè)有些同學(xué)忘記了： 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,問題一：科學(xué)計(jì)數(shù)法的格式,不知道？ e E ,用%e : 用 %.2e,如何實(shí)現(xiàn)
26、格式要求？,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,方法二：尾數(shù)和指數(shù)分開控制格式 a=(1.0*n*n*n+3.0*n*n+2.0*n)/6.0; b=log10(a); p
27、rintf(%.2lf,a/pow(10,b)); printf(E%dn,b);,2020/9/1,66,Any question?,2020/9/1,67,課后任務(wù)：,1004、1005、1008、1009 、1060 10121014、10191021 、1061 1049、1178、1108、1030 1071、1597,2020/9/1,68,提示：關(guān)于Presentation Error 的錯(cuò)誤,2016 輸出n個(gè)數(shù)，用空格隔開 常見錯(cuò)誤：for(i=1;i<=n;i++) printf(“%d “,ai); printf(“n “); 最后一個(gè)數(shù)之后也有空格造成
28、 Presentation Error錯(cuò)誤,2020/9/1,69,解決辦法,1、方法一 for(i=1;i
ACM課件(lecture02)老少皆宜數(shù)學(xué)題.ppt
