淺談數(shù)形結(jié)合思想在信息學(xué)競(jìng)賽中的應(yīng)用

1、淺談數(shù)形結(jié)合思想在信息學(xué)競(jìng)賽中的應(yīng)用,安徽 周源,引子,數(shù)與形是數(shù)學(xué)中兩個(gè)最古老而又最基本的對(duì)象數(shù)形結(jié)合又是一種重要的數(shù)學(xué)思想在算法和程序設(shè)計(jì)中，巧妙地運(yùn)用數(shù)形結(jié)合思想，可以順利的破解問題，化難為易，找到問題的解題思路。,數(shù)形結(jié)合思想常包括以下幾個(gè)方面：以形助數(shù)[例一]Raney的證明[例二]最大平均值問題以數(shù)助形[例三]畫室,以形助數(shù),繁雜代數(shù)關(guān)系后常隱藏著豐富的幾何背景借助背景圖形的性質(zhì)，可以使原本復(fù)雜的數(shù)量關(guān)

2、系和抽象的概念顯得直觀，從而找到設(shè)計(jì)算法的捷徑。,轉(zhuǎn)化,[例二]最大平均值問題(USACO),讀入一列正數(shù)，a1, a2, …, aN，以及數(shù)F 求一段長(zhǎng)度大于等于F且平均值最大的子串 定義若i≤j，ave(i, j) = (ai+…+aj) / (j-i+1)目標(biāo)：Max{ave(a, b) | a ≤ b-F+1}范圍：F≤N≤100 000 例如N=4的序列中，F(xiàn)=22, 5, 2, 5ave(2, 4) = (

3、5 + 2 + 5) / 3 = 4最大,初步分析,O(N2)算法枚舉一個(gè)b：稱為檢查點(diǎn)枚舉符合條件a：稱為被檢查點(diǎn)， 檢查集合條件即為 a ≤ b-F+1同時(shí)檢查ave(a, b),目標(biāo)圖形化,設(shè)部分和序列Si為{ai}前i項(xiàng)和，S0=0ave(i, j) = [Sj - Si-1] /[j - (i-1)]過兩點(diǎn)的直線：Pi-1(i-1, Si-1)，Pj(j, Sj)問題轉(zhuǎn)化：

4、平面上已知N+1個(gè)點(diǎn)，Pi(i, Si)，0≤i≤N求橫向距離大于等于F的兩點(diǎn)連線的最大斜率,斜率公式！,目標(biāo)圖形化,數(shù)列{ai}=(2, 5, 2, 5)，F(xiàn)=2部分和{Si}=(0, 2, 7, 9, 14),,,y,x,,,,,,(0, 0),(1, 2),(2, 7),(3, 9),(4, 14),,ave(2, 4) =k(P1P4)=4,構(gòu)造下凸折線,考察檢查點(diǎn)Z三個(gè)被檢查點(diǎn)從左到右三個(gè)點(diǎn)A, B, C若B是上凸

5、點(diǎn)？,,構(gòu)造下凸折線,若B不多余k(BZ)有可能最大若k(BZ)大于k(AZ)Z在1號(hào)區(qū)域若k(BZ)大于k(CZ)Z在2號(hào)區(qū)域若k(BZ)最大Z在陰影重疊區(qū)域!與B在Z左方矛盾B多余,結(jié)論：每個(gè)點(diǎn)的檢查集合只需要保留一個(gè)下凸函數(shù)即可在檢查集合中查找斜率最大點(diǎn)，即尋找切點(diǎn),,維護(hù)下凸折線,目標(biāo)：得到每一個(gè)檢查集合的下凸折線類似于求凸包過程線形時(shí)間內(nèi)完成！,,,y,x,,,,,,,,,,,,,,,,,,,,,,,,

6、,,P0,PF,最后的優(yōu)化：利用單調(diào)性,每次如何尋找切線？二分法：O(log2N)利用折線斜率單調(diào)性：O(1)更快，更簡(jiǎn)單請(qǐng)同學(xué)們自行思考,,,y,x,,,,,,,,,,,Z,,A,[例二]最大平均值問題(USACO),小結(jié)一開始就確立了以平面幾何為思考工具的正確路線重要結(jié)論：檢查集合中有用的點(diǎn)構(gòu)成一個(gè)下凸函數(shù)類似于計(jì)算幾何中求凸包的方法維護(hù)一個(gè)下凸折線 利用下凸函數(shù)斜率單調(diào)性得到找切線的簡(jiǎn)單方法,圍繞平面幾

7、何為中心，以斜率為主線整個(gè)解題過程一氣呵成避免了令人頭暈的代數(shù)式變換堪稱以形助數(shù)的經(jīng)典例題。,以數(shù)助形,一些試題給出的描述中圖形極為復(fù)雜，容易使選手陷入“迷魂陣”以數(shù)助形，一舉抓住其本質(zhì)特征，不失為解題的一種好方法。,轉(zhuǎn)化,[例三]畫室(POI oi V Stage I),定義尺寸為0的方陣為一個(gè)1*1的矩陣，在其唯一的一個(gè)方格中有一個(gè)小孔。對(duì)于i>0，遞歸的定義尺寸為i的方陣：,尺寸為2的方陣,尺寸為0的方陣,[例三]

8、畫室(POI oi V Stage I),已知尺寸N，和兩個(gè)參數(shù)X和Y準(zhǔn)備兩個(gè)尺寸為N的方陣疊放在一起上面的方陣右移X列，上移Y行求兩個(gè)方陣有多少個(gè)公共的孔？如N=2, X=2, Y=2有3個(gè)公共孔,初步分析,直接分析兩個(gè)方陣相交后的情況是可行的 集訓(xùn)隊(duì)前輩解題報(bào)告的一個(gè)附圖結(jié)論：“形”的路子很坎坷,目標(biāo)數(shù)值化,將行列按圖示方法從0開始編號(hào)每個(gè)方格都有唯一坐標(biāo)P(x, y)P(x, y)內(nèi)有小孔?？,列：0 　1

9、 　 2 　3 ?,行：0 　1 　 2 　3 ?,目標(biāo)數(shù)值化,將x, y化為二進(jìn)制a1a2a3…aN 和 b1b2b3…bN考察a1和b1對(duì)方格位置的影響a1=0且b1=1時(shí)方格內(nèi)必?zé)o孔！方格的有孔性質(zhì)當(dāng)且僅當(dāng)不存在1≤i≤N滿足ai=0且bi=1時(shí)方格P內(nèi)有小孔。,(a1, b1)分布圖,動(dòng)態(tài)規(guī)劃解題,題目即求滿足下列條件的方格P(x, y)個(gè)數(shù)0≤x, y，x+X, y+Y≤2N-1

10、(x, y)，(x+X, y+Y)都滿足有孔性質(zhì) 算法簡(jiǎn)述以位數(shù)為階段通過記錄x+X和y+Y進(jìn)位情況保證無后效性時(shí)間復(fù)雜度：O(N)空間復(fù)雜度：O(1),簡(jiǎn)單的動(dòng)態(tài)規(guī)劃算法！,[例三]畫室(POI oi V Stage I),小結(jié)“形”：情況復(fù)雜，不宜討論“數(shù)”：方格的有孔性質(zhì)和有公共孔性質(zhì)更簡(jiǎn)單的解題面對(duì)復(fù)雜的圖形化形歸數(shù)往往是抓住題目要害的好方法,總結(jié),數(shù),形,客觀事物,數(shù)學(xué),數(shù)形結(jié)合思想,抽象,,總結(jié),數(shù)

11、,形,數(shù)形結(jié)合思想,[例三]畫室,[例二]最大平均值問題,互相轉(zhuǎn)化,辯證矛盾關(guān)系,多元性,個(gè)體差異性,解法不唯一但是較好的,一定程度上唯一的解法,本質(zhì)化工具,形象化工具,不同的人對(duì)難度感覺不同,以形助數(shù),以數(shù)助形,總結(jié),數(shù),形,數(shù)形　　思想,辯證矛盾關(guān)系,多元性,個(gè)體差異性,將抽象的數(shù)學(xué)、計(jì)算機(jī)語言與直觀的圖形結(jié)合起來將抽象思維與形象思維結(jié)合起來實(shí)現(xiàn)抽象概念與具體形象的聯(lián)系和轉(zhuǎn)化,結(jié)合,更快更好更簡(jiǎn)單的解決實(shí)際問題,謝謝大家,T