ACM(lecture-02)老少皆宜數(shù)學題PPT優(yōu)秀課件

《ACM(lecture-02)老少皆宜數(shù)學題PPT優(yōu)秀課件》由會員分享，可在線閱讀，更多相關(guān)《ACM(lecture-02)老少皆宜數(shù)學題PPT優(yōu)秀課件（46頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、ACM程序設計程序設計杭州電子科技大學 劉春英7/3/20222第二講第二講老少皆宜之數(shù)學題老少皆宜之數(shù)學題7/3/20223今天，今天，你你 了嗎？了嗎？AC7/3/20224每周一星（每周一星（1）：）：亦紛菲幻劍亦紛菲幻劍 7/3/20225開胃羹（開胃羹（1）n幾個常用單詞：幾個常用單詞：1 1、vertex ( vertices ) vertex ( vertices ) 頂點頂點2 2、polygon polygon 多邊形多邊形3 3、convex convex 凸的凸的4 4、concave concave 凹的凹的5 5、segment (segment (線線) )段（段（

2、n n）; ;分割（分割（v v）7/3/20226開胃羹（開胃羹（2）n再來幾個：再來幾個：1 1、integer integer 整數(shù)整數(shù)2 2、positive positive 正的正的3 3、negative (adj)negative (adj)負的負的; (n); (n)負數(shù)負數(shù)4 4、factorial (n)factorial (n)階乘階乘;(adj);(adj)因子的，階乘的因子的，階乘的5 5、digital (n)digital (n)數(shù)字數(shù)字;(adj);(adj)數(shù)字的數(shù)字的7/3/20227ACM數(shù)學題特點分析數(shù)學題特點分析:n題意容易理解題意容易理解n算法相對

3、簡單（有些很難的?。┧惴ㄏ鄬唵危ㄓ行┖茈y的?。﹏編程比較容易編程比較容易nACM/ICPCACM/ICPC入門練習的好選擇入門練習的好選擇下面，分類介紹：下面，分類介紹：7/3/20228從首屆從首屆“舜宇舜宇”杯杯說起說起7/3/20229比賽背景比賽背景由于前一年的邀請賽很多學校沒有做出一道由于前一年的邀請賽很多學校沒有做出一道題，所以，這次的比賽特意準備了幾道簡單題，所以，這次的比賽特意準備了幾道簡單的題目，目的就是讓大多數(shù)的學校都能拿個的題目，目的就是讓大多數(shù)的學校都能拿個氣球回去，也好有個交待，于是有氣球回去，也好有個交待，于是有7/3/202210第一類第一類傻傻 瓜瓜 型型7/

4、3/20221110041004: : Let the Balloon Rise Let the Balloon Rise7/3/202212題目評述：題目評述：1. 一個讓你看到后興奮的題目一個讓你看到后興奮的題目 2. 2. 只要懂點只要懂點C C或者或者C+C+，就可解決該問題。，就可解決該問題。7/3/20221310041004題目分析：題目分析：n該題算法思想比較簡單，就是對輸入的字符該題算法思想比較簡單，就是對輸入的字符串進行比較和統(tǒng)計。值得注意的一點是：串進行比較和統(tǒng)計。值得注意的一點是：n如果用如果用C C語言來寫，要注意可能會把第一個數(shù)語言來寫，要注意可能會把第一個數(shù)字后的

5、字后的“回車符回車符”誤認為是第一個串，字符誤認為是第一個串，字符串的比較也要用函數(shù)和循環(huán)語句。串的比較也要用函數(shù)和循環(huán)語句。n而而C+C+則在處理字符串方面較為方便。則在處理字符串方面較為方便。7/3/20221410081008: Elevator: Elevator7/3/202215 實際上，這是本次比賽最簡單的一題，浙大、實際上，這是本次比賽最簡單的一題，浙大、浙工大等當時訓練水平相對較高的學?；旧险愎ご蟮犬敃r訓練水平相對較高的學?；旧?010分鐘之內(nèi)解決該題，這也是一個沒有算法的分鐘之內(nèi)解決該題，這也是一個沒有算法的題目。題目。 這種題目大家不會錯過的這種題目大家不會錯過的題目

6、評述題目評述：7/3/202217第二類第二類基基 本本 型型7/3/2022181009: FatMouse Trade1009: FatMouse Trade7/3/202219題目特點：題目特點： 這個題目比前面兩個題目稍難，但是屬于能一眼看出解決辦法的題目。只要靜下心，還是比較容易解決的。7/3/20222010091009算法分析：算法分析：n輸入（J , F 放入數(shù)組）n對數(shù)組排序（按效益，降序）n輸出（按效益高低有序交易）7/3/202221第三類第三類技技 巧巧 型型7/3/202222小錘摳縫小錘摳縫先來看一個簡單的題目鋪墊一下：先來看一個簡單的題目鋪墊一下：7/3/2022

7、231021 Fibonacci 1021 Fibonacci AgainAgain 7/3/202224題目分析：題目分析：n能被能被3 3整除的整數(shù)的特點？整除的整數(shù)的特點？還要看程序嗎？還要看程序嗎？n如果兩個數(shù)的和能被如果兩個數(shù)的和能被3 3整除，這兩個數(shù)有什么整除，這兩個數(shù)有什么特點？特點？n關(guān)于能否被關(guān)于能否被3 3整除，這兩個數(shù)一共有多少種組整除，這兩個數(shù)一共有多少種組合？合？7/3/202225Hdoj_1021Hdoj_1021程序清單：程序清單：n#includenint main()nn long n;n while(scanf(%ld,&n) != EOF)n if (

8、n%8=2 | n%8=6)n printf(yesn);n elsen printf(non);nreturn 0;n7/3/202226回到正題回到正題大錘搞定大錘搞定7/3/202227Problem B: Number SequenceProblem B: Number Sequence7/3/202228題目特點：題目特點：這個題目是一個比較典型的這個題目是一個比較典型的ACMACM競賽題，競賽題，盡管在真正的大賽中這個題目可能算比較簡盡管在真正的大賽中這個題目可能算比較簡單的，但在本次比賽中，本題難度屬于中等，單的，但在本次比賽中，本題難度屬于中等，可以說，能做出本題的隊伍基本都有

9、二等獎可以說，能做出本題的隊伍基本都有二等獎以上。以上。但如果不認真分析，有可能會掉入陷阱。但如果不認真分析，有可能會掉入陷阱。7/3/202229Question:Question:暴力能解決問題嗎？暴力能解決問題嗎？7/3/202230拒絕暴力拒絕暴力7/3/202231題目分析：題目分析：對于這種題目，千萬不能蠻干！實際上，對于這種題目，千萬不能蠻干！實際上，有經(jīng)驗的同學看到本題目的數(shù)據(jù)規(guī)模，很快就有經(jīng)驗的同學看到本題目的數(shù)據(jù)規(guī)模，很快就能知道：這類題目有規(guī)律可循。能知道：這類題目有規(guī)律可循。7/3/202232現(xiàn)在對這題有什么想法現(xiàn)在對這題有什么想法?7/3/202233第四類第四類紙

10、老虎型紙老虎型7/3/202234HDOJ_1071 The AreaHDOJ_1071 The Area 7/3/202235第一眼：傻了第一眼：傻了7/3/202236再一看再一看7/3/202237拋物線公式：拋物線公式：y=ax2+bx+cy=ax2+bx+c已知三點已知三點 - -a a、b b、c c 系數(shù)系數(shù)公式已知公式已知 - - 如何求面積？如何求面積？會簡單積分嗎？會簡單積分嗎？分析過程：分析過程：該你思該你思考了考了感覺怎感覺怎么樣？么樣？7/3/202239思考題：思考題：（2006/3/4 HDOJ2006/3/4 HDOJ的練習賽題目）的練習賽題目）7/3/2022

11、40要點分析：要點分析：1 1、暴力的復雜度是多少？、暴力的復雜度是多少？2 2、哪些陷阱？、哪些陷阱？3 3、關(guān)鍵在哪？、關(guān)鍵在哪？4 4、順利應該多長時間？、順利應該多長時間？7/3/202241數(shù)學公式數(shù)學公式: :1 1、這個大家都會：、這個大家都會：1+2+3+4+n=n(n+1)/21+2+3+4+n=n(n+1)/22 2、這個有些同學忘記了：、這個有些同學忘記了：1 1* *1+21+2* *2+32+3* *3+n3+n* *n=n(n+1)(2n+1)/6n=n(n+1)(2n+1)/63 3、合并后得到、合并后得到n(n+1)(n+2)/3n(n+1)(n+2)/37/3

12、/202242Any question?7/3/202243課后任務：課后任務：一、一、DIYDIY在線作業(yè)在線作業(yè)(2):(2):2008ACM ProgrammingExercise（2）_Math 二、常規(guī)練習（包含以上作業(yè)）二、常規(guī)練習（包含以上作業(yè)）10041004、10051005、10081008、1009 1009 、106010601012101210141014、101910191021 1021 、1061106110491049、1066 1066 、11781178、11081108、1030 1030 10711071、159715977/3/202244下一講：下一講：遞推求解遞推求解7/3/202245Welcome to HDOJWelcome to HDOJThank Thank You You 個人觀點供參考，歡迎討論