ACM課件(lecture02)老少皆宜數(shù)學題.ppt

《ACM課件(lecture02)老少皆宜數(shù)學題.ppt》由會員分享，可在線閱讀，更多相關《ACM課件(lecture02)老少皆宜數(shù)學題.ppt（75頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、ACM程序設計,2020/9/1,2,第二講,老少皆宜之數(shù)學題,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 整數(shù) 2、positive 正的 3、negative (adj)負的; (n)負數(shù) 4、factorial (n)階乘;(adj)因子的，階乘的 5、digital (n)數(shù)字;(adj)

2、數(shù)字的,2020/9/1,6,ACM數(shù)學題特點分析:,題意容易理解 算法相對簡單（有些很難的?。。?編程比較容易 ACM/ICPC入門練習的好選擇 下面，分類介紹：,2020/9/1,7,從首屆“舜宇”杯說起,2020/9/1,8,比賽背景,由于前一年的邀請賽很多學校沒有做出一道題，所以，這次的比賽特意準備了幾道簡單的題目，目的就是讓大多數(shù)的學校都能拿個氣球回去，也好有個交待，于是有,,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,題目評述：,1. 一個讓你看到后興奮的題目,2. 只要懂點C或者C++，就可解決該問題。,2020/9/1,16,1004題目分析：,該題算法思想比較簡單，就是對輸入的字符串進行比較和統(tǒng)計。值得注意的一點是： 如果用C語言來寫，要注意可能會把第一個數(shù)字后的“回車符”誤認為是第一個串，字符串的比較也要用函數(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,實際上，這是本次比賽最簡單的一題，浙大、浙工大等當時訓練水平相對較高的學?；旧?0分鐘之內解決該題，這也是一個沒有算法的題目。 這種題目大家不會錯過的,題目評述：,不要分析了吧,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,題目特點：,這個題目比前面兩個題目稍難，但是屬于能一眼看出解決辦法的題目。只要靜下心，還是比較容易解決的。,2020/9/1,31,1009算法分析：,輸入（J , F 放入數(shù)組） 對數(shù)組排序（按效益，降序） 輸出（按效益高低有序交易）,2020/9/1,32,第三類,技 巧 型,2020/9/1,33,小錘摳縫,先來看一個簡單的題目鋪墊一下：,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ù)的特點？,如果兩個數(shù)的和能被3整除，這兩個數(shù)有什么特點？,關于能否被3整除，這兩個數(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,題目特點：,這個題目是一個比較典型的

19、ACM競賽題，盡管在真正的大賽中這個題目可能算比較簡單的，但在本次比賽中，本題難度屬于中等，可以說，能做出本題的隊伍基本都有二等獎以上。 但如果不認真分析，有可能會掉入陷阱。,2020/9/1,46,Question:,暴力能解決問題嗎？,2020/9/1,47,拒絕暴力,2020/9/1,48,題目分析：,對于這種題目，千萬不能蠻干！實際上，有經(jīng)驗的同學看到本題目的數(shù)據(jù)規(guī)模，很快就能知道：這類題目有規(guī)律可循。,2020/9/1,49,現(xiàn)在對這題有什么想法,???,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,已知三點 -a、b、c 系數(shù),公式已知 - 如何求面積？,會簡單積分嗎？,分析過程：,該你思考了,感覺怎么樣？,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,要點分析：,1、暴力的復雜度是多少？ 2、哪些陷阱？ 3、關鍵在哪？ 4、順利應該多長時間？,2020/9/1,62,數(shù)學公式:,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,問題一：科學計數(shù)法的格式,不知道？ e E ,用%e : 用 %.2e,如何實現(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,課后任務：,1004、1005、1008、1009 、1060 10121014、10191021 、1061 1049、1178、1108、1030 1071、1597,2020/9/1,68,提示：關于Presentation Error 的錯誤,2016 輸出n個數(shù)，用空格隔開 常見錯誤：for(i=1;i<=n;i++) printf(“%d “,ai); printf(“n “); 最后一個數(shù)之后也有空格造成

28、 Presentation Error錯誤,2020/9/1,69,解決辦法,1、方法一 for(i=1;i