最新(lecture_03)老少皆宜數(shù)學(xué)題

1、2024/3/29,1,,ACM 程序設(shè)計(jì),2024/3/29,2,今天，,你 了嗎？,AC,2024/3/29,3,每周一星（2）：,04916321,2024/3/29,4,開胃羹（1）,幾個(gè)常用單詞：1、vertex ( vertices ) 頂點(diǎn)2、polygon 多邊形3、convex 凸的4、concave 凹的5、segment (線)段（n）;分割（v）,2024/3/29,5,

2、開胃羹（2）,再來幾個(gè)：1、integer 整數(shù)2、positive 正的3、negative (adj)負(fù)的; (n)負(fù)數(shù)4、factorial (n)階乘; (adj)因子的，階乘的5、digital (n)數(shù)字; (adj)數(shù)字的,2024/3/29,6,第三講,老少皆宜之?dāng)?shù)學(xué)題,2024/3/29,7,ACM數(shù)學(xué)題特點(diǎn)分析:,題意容易理解算法相對(duì)簡單（有些很難的！?。?/p>

3、編程比較容易ACM/ICPC入門練習(xí)的好選擇下面，分類介紹：,2024/3/29,8,從首屆“舜宇”杯說起,2024/3/29,9,比賽背景,由于前一年的邀請(qǐng)賽很多學(xué)校沒有做出一道題，所以，這次的比賽特意準(zhǔn)備了幾道簡單的題目，目的就是讓大多數(shù)的學(xué)校都能拿個(gè)氣球回去，也好有個(gè)交待，于是有…,,2024/3/29,10,第一類,弱 智 型,Problem A: Let the Balloon Rise,2024/3/29,12,題

4、目評(píng)述：,1. 一個(gè)讓你看到后興奮的題目…,2. 只要懂點(diǎn)C或者C++，就可解決該問題。,2024/3/29,13,1004題目分析：,該題算法思想比較簡單，就是對(duì)輸入的字符串進(jìn)行比較和統(tǒng)計(jì)。值得注意的一點(diǎn)是：如果用C語言來寫，要注意可能會(huì)把第一個(gè)數(shù)字后的“回車符”誤認(rèn)為是第一個(gè)串，字符串的比較也要用函數(shù)和循環(huán)語句。而C++則在處理字符串方面較為方便。,Problem E: Elevator,2024/3/29,15,實(shí)際上，這是本

5、次比賽最簡單的一題，浙大、浙工大和寧波理工等高校的隊(duì)伍基本上10分鐘之內(nèi)解決該題，這也是一個(gè)沒有算法的題目。 這種題目大家不會(huì)錯(cuò)過的…,題目評(píng)述：,2024/3/29,16,不要分析了吧…,2024/3/29,17,第二類 基 本 型,2024/3/29,18,Problem F: FatMouse' Trade,2024/3/29,19,題目特點(diǎn)：,這個(gè)題目比前面兩個(gè)題目稍難，但是屬于能一眼看出解決辦法的題目。只

6、要靜下心，還是比較容易解決的。,2024/3/29,20,1009算法分析：,輸入（J , F 放入數(shù)組）對(duì)數(shù)組排序（按效益，降序）輸出（按效益高低有序交易）,2024/3/29,21,第三類 技 巧 型,2024/3/29,22,先來看一個(gè)簡單的題目鋪墊一下:,1021 Fibonacci Again,2024/3/29,24,題目分析：,能被3整除的整數(shù)的特點(diǎn)？,還要看程序嗎？,如果兩個(gè)數(shù)的和能被3整除，這兩個(gè)數(shù)有什么特

7、點(diǎn)？,關(guān)于能否被3整除，這兩個(gè)數(shù)一共有多少種組合？,2024/3/29,25,Hdoj_1021程序清單：,#includeint main(){ long n; while(scanf("%ld",&n) != EOF) if (n%8==2 || n%8==6) printf("yes\n"); else printf("

8、;no\n");return 0;},2024/3/29,26,回到正題,,Problem B: Number Sequence,2024/3/29,28,題目特點(diǎn)：,這個(gè)題目是一個(gè)比較典型的ACM競賽題，盡管在真正的大賽中這個(gè)題目可能算比較簡單的，但在本次比賽中，本題難度屬于中等，可以說，能做出本題的隊(duì)伍基本都有二等獎(jiǎng)以上。但如果不認(rèn)真分析，有可能會(huì)掉入陷阱。,2024/3/29,29,Question:,暴力能

9、解決問題嗎？,2024/3/29,30,Why?,2024/3/29,31,題目分析：,對(duì)于這種題目，千萬不能蠻干！實(shí)際上，有經(jīng)驗(yàn)的同學(xué)看到本題目的數(shù)據(jù)規(guī)模，很快就能知道：這類題目有規(guī)律可循。,2024/3/29,32,現(xiàn)在對(duì)這題有什么想法,???,2024/3/29,33,第四類 紙老虎型,HDOJ_1071 The Area,第一眼：傻了…,2024/3/29,36,第二眼 笑了… ?,2024/3/29,37,拋物線公式：y

10、=ax^2+bx+c,已知三點(diǎn) -〉a、b、c 系數(shù),公式已知 - 〉如何求面積？,會(huì)簡單積分嗎？,2024/3/29,38,該你思考了…,感覺怎么樣？,2024/3/29,39,思考題(1)：,（Ural Collegiate Programming Contest 1998 ） http://acm.hziee.edu.cn/showproblem.php?pid=1030,題目大意：,Input Input contain

11、s two integer numbers M and N in the range from 1 to 1000000000 separated with space(s).Output Output should contain the length of the shortest route.Sample Input 6 12 Sample Output 3,2024/3/29,41,思考：,要輸出的結(jié)果和哪些因素

12、有關(guān)？請(qǐng)發(fā)表見解。,思考題(2)：,（3月4日HDOJ的練習(xí)賽題目）,2024/3/29,43,要點(diǎn)分析：,1、暴力的復(fù)雜度是多少？2、哪些陷阱？3、關(guān)鍵在哪？4、順利應(yīng)該多長時(shí)間？,2024/3/29,44,數(shù)學(xué)公式:,1、這個(gè)大家都會(huì)：1+2+3+4+…n=n(n+1)/22、這個(gè)有些同學(xué)忘記了： 1*1+2*2+3*3+…+n*n=n(n+1)(2n+1)/63、合并后得到n(n+1)(n+2)/3,202

13、4/3/29,45,Any question?,2024/3/29,46,課后作業(yè)（簡單數(shù)學(xué)題）,2024/3/29,47,HDOJ作業(yè)：,1004、1005、1008、1009、1108 、10491012（u Calculate e ） 1014（Uniform Generator ）1019（Least Common Multiple ）1020（Encoding ）1021 ( Fibonacci Again )