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

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

1、ACM程序設(shè)計(jì)程序設(shè)計(jì)杭州電子科技大學(xué) 劉春英7/3/20222第二講第二講老少皆宜之?dāng)?shù)學(xué)題老少皆宜之?dāng)?shù)學(xué)題7/3/20223今天，今天，你你 了嗎？了嗎？AC7/3/20224每周一星（每周一星（1）：）：亦紛菲幻劍亦紛菲幻劍 7/3/20225開胃羹（開胃羹（1）n幾個(gè)常用單詞：幾個(gè)常用單詞：1 1、vertex ( vertices ) vertex ( vertices ) 頂點(diǎn)頂點(diǎn)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再來幾個(gè)：再來幾個(gè)：1 1、integer integer 整數(shù)整數(shù)2 2、positive positive 正的正的3 3、negative (adj)negative (adj)負(fù)的負(fù)的; (n); (n)負(fù)數(shù)負(fù)數(shù)4 4、factorial (n)factorial (n)階乘階乘;(adj);(adj)因子的，階乘的因子的，階乘的5 5、digital (n)digital (n)數(shù)字?jǐn)?shù)字;(adj);(adj)數(shù)字的數(shù)字的7/3/20227ACM數(shù)學(xué)題特點(diǎn)分析數(shù)學(xué)題特點(diǎn)分析:n題意容易理解題意容易理解n算法相對(duì)

3、簡(jiǎn)單（有些很難的！）算法相對(duì)簡(jiǎn)單（有些很難的?。﹏編程比較容易編程比較容易nACM/ICPCACM/ICPC入門練習(xí)的好選擇入門練習(xí)的好選擇下面，分類介紹：下面，分類介紹：7/3/20228從首屆從首屆“舜宇舜宇”杯杯說起說起7/3/20229比賽背景比賽背景由于前一年的邀請(qǐng)賽很多學(xué)校沒有做出一道由于前一年的邀請(qǐng)賽很多學(xué)校沒有做出一道題，所以，這次的比賽特意準(zhǔn)備了幾道簡(jiǎn)單題，所以，這次的比賽特意準(zhǔn)備了幾道簡(jiǎn)單的題目，目的就是讓大多數(shù)的學(xué)校都能拿個(gè)的題目，目的就是讓大多數(shù)的學(xué)校都能拿個(gè)氣球回去，也好有個(gè)交待，于是有氣球回去，也好有個(gè)交待，于是有7/3/202210第一類第一類傻傻 瓜瓜 型型7/

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

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

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

7、231021 Fibonacci 1021 Fibonacci AgainAgain 7/3/202224題目分析：題目分析：n能被能被3 3整除的整數(shù)的特點(diǎn)？整除的整數(shù)的特點(diǎn)？還要看程序嗎？還要看程序嗎？n如果兩個(gè)數(shù)的和能被如果兩個(gè)數(shù)的和能被3 3整除，這兩個(gè)數(shù)有什么整除，這兩個(gè)數(shù)有什么特點(diǎn)？特點(diǎn)？n關(guān)于能否被關(guān)于能否被3 3整除，這兩個(gè)數(shù)一共有多少種組整除，這兩個(gè)數(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題目特點(diǎn)：題目特點(diǎn)：這個(gè)題目是一個(gè)比較典型的這個(gè)題目是一個(gè)比較典型的ACMACM競(jìng)賽題，競(jìng)賽題，盡管在真正的大賽中這個(gè)題目可能算比較簡(jiǎn)盡管在真正的大賽中這個(gè)題目可能算比較簡(jiǎn)單的，但在本次比賽中，本題難度屬于中等，單的，但在本次比賽中，本題難度屬于中等，可以說，能做出本題的隊(duì)伍基本都有

9、二等獎(jiǎng)可以說，能做出本題的隊(duì)伍基本都有二等獎(jiǎng)以上。以上。但如果不認(rèn)真分析，有可能會(huì)掉入陷阱。但如果不認(rèn)真分析，有可能會(huì)掉入陷阱。7/3/202229Question:Question:暴力能解決問題嗎？暴力能解決問題嗎？7/3/202230拒絕暴力拒絕暴力7/3/202231題目分析：題目分析：對(duì)于這種題目，千萬不能蠻干！實(shí)際上，對(duì)于這種題目，千萬不能蠻干！實(shí)際上，有經(jīng)驗(yàn)的同學(xué)看到本題目的數(shù)據(jù)規(guī)模，很快就有經(jīng)驗(yàn)的同學(xué)看到本題目的數(shù)據(jù)規(guī)模，很快就能知道：這類題目有規(guī)律可循。能知道：這類題目有規(guī)律可循。7/3/202232現(xiàn)在對(duì)這題有什么想法現(xiàn)在對(duì)這題有什么想法?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已知三點(diǎn)已知三點(diǎn) - -a a、b b、c c 系數(shù)系數(shù)公式已知公式已知 - - 如何求面積？如何求面積？會(huì)簡(jiǎn)單積分嗎？會(huì)簡(jiǎn)單積分嗎？分析過程：分析過程：該你思該你思考了考了感覺怎感覺怎么樣？么樣？7/3/202239思考題：思考題：（2006/3/4 HDOJ2006/3/4 HDOJ的練習(xí)賽題目）的練習(xí)賽題目）7/3/2022

11、40要點(diǎn)分析：要點(diǎn)分析：1 1、暴力的復(fù)雜度是多少？、暴力的復(fù)雜度是多少？2 2、哪些陷阱？、哪些陷阱？3 3、關(guān)鍵在哪？、關(guān)鍵在哪？4 4、順利應(yīng)該多長(zhǎng)時(shí)間？、順利應(yīng)該多長(zhǎng)時(shí)間？7/3/202241數(shù)學(xué)公式數(shù)學(xué)公式: :1 1、這個(gè)大家都會(huì)：、這個(gè)大家都會(huì)：1+2+3+4+n=n(n+1)/21+2+3+4+n=n(n+1)/22 2、這個(gè)有些同學(xué)忘記了：、這個(gè)有些同學(xué)忘記了：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課后任務(wù)：課后任務(wù)：一、一、DIYDIY在線作業(yè)在線作業(yè)(2):(2):2008ACM ProgrammingExercise（2）_Math 二、常規(guī)練習(xí)（包含以上作業(yè)）二、常規(guī)練習(xí)（包含以上作業(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 個(gè)人觀點(diǎn)供參考，歡迎討論