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

1、IOI2004冬令營演示文稿安徽周源IOI2004冬令營演示文稿安徽周源 數(shù)與形是數(shù)學(xué)中兩個最古老而又最基本的對象 數(shù)形結(jié)合又是一種重要的數(shù)學(xué)思想 在算法和程序設(shè)計(jì)中，巧妙地運(yùn)用數(shù)形結(jié)合思想，可以順利的破解問題，化難為易，找到問題的解題思路。 數(shù)形結(jié)合思想常包括以下幾個方面： 以形助數(shù) 例一Raney的證明 例二最大平均值問題 以數(shù)助形 例三畫室IOI2004冬令營演示文稿安徽周源 繁雜代數(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冬令營演示文稿安徽周源讀入一列正數(shù)，a1, a2, , aN，以及數(shù)F 求一段長度大于等于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冬令營演示文稿安徽周源O(N2)算法枚舉一個b：稱為檢查點(diǎn)檢查點(diǎn)枚舉符合條件a：稱為被檢查點(diǎn)被檢查點(diǎn)， 檢查集合檢查集合條件即為 a b-F+1同時檢查ave(a, b)IOI2004

3、冬令營演示文稿安徽周源設(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個點(diǎn)，Pi(i, Si)，0iN求橫向距離大于等于F的兩點(diǎn)連線的最大斜率斜率公式！斜率公式！IOI2004冬令營演示文稿安徽周源數(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冬令營演示文稿安徽周源考察檢查點(diǎn)Z三個被檢查

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

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

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

7、從從0開始開始編號每個方格都有唯一坐標(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冬令營演示文稿安徽周源將x, y化為二進(jìn)

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

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