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

1、IOI2004冬令營(yíng)演示文稿安徽周源IOI2004冬令營(yíng)演示文稿安徽周源 數(shù)與形是數(shù)學(xué)中兩個(gè)最古老而又最基本的對(duì)象 數(shù)形結(jié)合又是一種重要的數(shù)學(xué)思想 在算法和程序設(shè)計(jì)中，巧妙地運(yùn)用數(shù)形結(jié)合思想，可以順利的破解問題，化難為易，找到問題的解題思路。 數(shù)形結(jié)合思想常包括以下幾個(gè)方面： 以形助數(shù) 例一Raney的證明 例二最大平均值問題 以數(shù)助形 例三畫室IOI2004冬令營(yíng)演示文稿安徽周源 繁雜代數(shù)關(guān)系后常隱藏著豐富的幾何背景 借助背景圖形的性質(zhì)，可以使原本復(fù)雜的數(shù)量關(guān)系和抽象的概念顯得直觀，從而找到設(shè)計(jì)算法的捷徑。 數(shù)數(shù)？? ?opt(N)=maxf(i)=f(i-1)+f(i-2)形！形！直線、圓

2、轉(zhuǎn)化轉(zhuǎn)化IOI2004冬令營(yíng)演示文稿安徽周源讀入一列正數(shù)，a1, a2, , aN，以及數(shù)F 求一段長(zhǎng)度大于等于F且平均值最大平均值最大的子串 定義若ij，ave(i, j) = (ai+aj) / (j-i+1)目標(biāo)：Maxave(a, b) | a b-F+1范圍：FN100 000 例如N=4的序列中，F(xiàn)=22, 5, 2, 5ave(2, 4) = (5 + 2 + 5) / 3 = 4最大IOI2004冬令營(yíng)演示文稿安徽周源O(N2)算法枚舉一個(gè)b：稱為檢查點(diǎn)檢查點(diǎn)枚舉符合條件a：稱為被檢查點(diǎn)被檢查點(diǎn)， 檢查集合檢查集合條件即為 a b-F+1同時(shí)檢查ave(a, b)IOI2004

3、冬令營(yíng)演示文稿安徽周源設(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)化：平面上已知N+1個(gè)點(diǎn)，Pi(i, Si)，0iN求橫向距離大于等于F的兩點(diǎn)連線的最大斜率斜率公式！斜率公式！IOI2004冬令營(yíng)演示文稿安徽周源數(shù)列ai=(2, 5, 2, 5)，F(xiàn)=2部分和Si=(0, 2, 7, 9, 14)yx(0, 0)(1, 2)(2, 7)(3, 9)(4, 14)ave(2, 4) =k(P1P4)=4距離3IOI2004冬令營(yíng)演示文稿安徽周源考察檢查點(diǎn)Z三個(gè)被檢查

4、點(diǎn)從左到右三個(gè)點(diǎn)A, B, C若B是上凸點(diǎn)？yxIOI2004冬令營(yíng)演示文稿安徽周源若B不多余 k(BZ)有可能最大有可能最大若k(BZ)大于k(AZ) Z在在1號(hào)區(qū)域號(hào)區(qū)域若k(BZ)大于k(CZ) Z在在2號(hào)區(qū)域號(hào)區(qū)域若k(BZ)最大 Z在陰影重疊區(qū)域在陰影重疊區(qū)域!與B在Z左方矛盾 B多余多余結(jié)論：結(jié)論：每個(gè)點(diǎn)的檢查集合只需要保留一個(gè)下凸函數(shù)下凸函數(shù)即可在檢查集合中查找斜率最大點(diǎn)，即尋找切點(diǎn)切點(diǎn)yxIOI2004冬令營(yíng)演示文稿安徽周源目標(biāo)：目標(biāo)：得到每一個(gè)檢查集合的下凸折線類似于求凸包過程線形時(shí)間內(nèi)完成！yxP0PFIOI2004冬令營(yíng)演示文稿安徽周源每次如何尋找切線？二分法：O(log

5、2N)利用折線斜率單調(diào)斜率單調(diào)性性：O(1)更快，更簡(jiǎn)單請(qǐng)同學(xué)們自行思考yxZAIOI2004冬令營(yíng)演示文稿安徽周源小結(jié) 一開始就確立了以平面幾平面幾何何為思考工具的正確路線 重要結(jié)論：重要結(jié)論：檢查集合中有用的點(diǎn)構(gòu)成一個(gè)下凸函數(shù) 類似于計(jì)算幾何中求凸包的方法維護(hù)一個(gè)下凸折線 利用下凸函數(shù)斜率單調(diào)性斜率單調(diào)性得到找切線的簡(jiǎn)單方法 圍繞平面幾何平面幾何為中心，以斜率斜率為主線 整個(gè)解題過程一氣呵成 避免了令人頭暈的代數(shù)式變換 堪稱以形助數(shù)的經(jīng)典例題。 IOI2004冬令營(yíng)演示文稿安徽周源 一些試題給出的描述中圖形極為復(fù)雜，容易使選手陷入“迷魂陣” 以數(shù)助形，一舉抓住其本質(zhì)特征，不失為解題的一種好

6、方法。形？形？數(shù)！數(shù)！x2+y2=1(10101)2轉(zhuǎn)化轉(zhuǎn)化IOI2004冬令營(yíng)演示文稿安徽周源定義尺寸為0的方陣為一個(gè)1*1的矩陣，在其唯一的一個(gè)方格中有一個(gè)小孔。對(duì)于i0，遞歸的定義尺寸為i的方陣：尺寸為2的方陣尺寸為0的方陣IOI2004冬令營(yíng)演示文稿安徽周源已知尺寸N，和兩個(gè)參數(shù)X和Y準(zhǔn)備兩個(gè)尺寸為N的方陣疊放在一起上面的方陣右移X列，上移Y行求兩個(gè)方陣有多少個(gè)公共的孔？如N=2, X=2, Y=2有3個(gè)公共孔IOI2004冬令營(yíng)演示文稿安徽周源直接分析兩個(gè)方陣相交后的情況是可行的 集訓(xùn)隊(duì)前輩解題報(bào)告的一個(gè)附圖結(jié)論：“形”的路子很坎坷IOI2004冬令營(yíng)演示文稿安徽周源將行列按圖示方法

7、從從0開始開始編號(hào)每個(gè)方格都有唯一坐標(biāo)P(x, y)P(x, y)內(nèi)有小孔？尺寸為2的方陣列：0 1 2 3 行：0 1 2 3 (0, 3) (1, 3)(0, 2) (1, 2)(2, 3) (3, 3)(2, 2) (3, 2)(0, 1) (1, 1)(0, 0) (1, 0)(2, 1) (3, 1)(2, 0) (3, 0)(0, 3) (1, 3)(0, 2) (1, 2)(2, 3) (3, 3)(2, 2) (3, 2)(0, 1) (1, 1)(0, 0) (1, 0)(2, 1) (3, 1)(2, 0) (3, 0)IOI2004冬令營(yíng)演示文稿安徽周源將x, y化為二進(jìn)

8、制a1a2a3aN 和 b1b2b3bN考察a1和b1對(duì)方格位置的影響a1=0且且b1=1時(shí)方格內(nèi)必?zé)o孔！時(shí)方格內(nèi)必?zé)o孔！方格的有孔性質(zhì)有孔性質(zhì)當(dāng)且僅當(dāng)不存在1iN滿足ai=0且bi=1時(shí)方格P內(nèi)有小孔。 (a1, b1)分布圖IOI2004冬令營(yíng)演示文稿安徽周源題目即求滿足下列條件的方格P(x, y)個(gè)數(shù)0 x, y，x+X, y+Y2N-1 (x, y)，(x+X, y+Y)都滿足有孔性質(zhì) 算法簡(jiǎn)述以位數(shù)為階段通過記錄x+X和y+Y進(jìn)位情況保證無(wú)后效性時(shí)間復(fù)雜度：O(N)空間復(fù)雜度：O(1)簡(jiǎn)單的動(dòng)態(tài)規(guī)劃算法！IOI2004冬令營(yíng)演示文稿安徽周源小結(jié)“形”：情況復(fù)雜，不宜討論“數(shù)”：方格的

9、有孔性質(zhì)和有公共孔性質(zhì)更簡(jiǎn)單的解題面對(duì)復(fù)雜的圖形化形歸數(shù)往往是抓住題目要害的好方法IOI2004冬令營(yíng)演示文稿安徽周源數(shù)形客觀事物數(shù)學(xué)數(shù)學(xué)數(shù)形結(jié)合思想抽象抽象IOI2004冬令營(yíng)演示文稿安徽周源數(shù)形數(shù)形結(jié)合思想例三例三畫室畫室例二例二最大平均值問題最大平均值問題互相轉(zhuǎn)化辯證矛盾關(guān)系辯證矛盾關(guān)系多元性多元性個(gè)體差異性個(gè)體差異性解法不唯一但是較好的一定程度上唯一的解法本質(zhì)化工具形象化工具不同的人對(duì)難度感覺不同以形助數(shù)以數(shù)助形IOI2004冬令營(yíng)演示文稿安徽周源數(shù)形數(shù)形思想辯證矛盾關(guān)系辯證矛盾關(guān)系多元性多元性個(gè)體差異性個(gè)體差異性將抽象的數(shù)學(xué)、計(jì)算機(jī)語(yǔ)言與直觀的圖形結(jié)合起來(lái)結(jié)合起來(lái)將抽象思維與形象思維結(jié)合起來(lái)結(jié)合起來(lái)實(shí)現(xiàn)抽象概念