算法合集之《淺談補(bǔ)集轉(zhuǎn)化思想在統(tǒng)計(jì)問題中的應(yīng)用》-文庫吧
2024-12-25 09:23 本頁面
【正文】 化思想在很多方面有著廣泛的應(yīng)用，讓我們來看看在解決統(tǒng)計(jì)問題方面它又有哪些精彩表現(xiàn)吧！ 例一 單色三角形問題（ POI9714 TRO） 題目大意 空間里 有 n 個(gè)點(diǎn)，任意三點(diǎn)不共線。每兩點(diǎn)之間都用紅色或黑色線段（只有一條，非紅即黑?。┻B接。如果一個(gè)三角形的三條邊同色，則稱這個(gè)三角形是單色三角形。對(duì)于給定的紅色線段的列表，找出單色三角形的個(gè)數(shù)。例如圖一中有5 個(gè)點(diǎn)， 10 條邊，形成 3 個(gè)單色三角形。 輸入點(diǎn)數(shù) n、紅色邊數(shù) m 以及這 m 條紅色的邊所連接的頂點(diǎn)標(biāo)號(hào)，輸出單色三角形個(gè)數(shù) R。 3=n=1000， 0=m=250000。 初步分析 很自然地，我們想到了如下算法：用一個(gè) 1000*1000 的數(shù)組記錄每兩個(gè)點(diǎn)之間邊的顏色，然后枚舉所有的三角形（這是通過枚舉三個(gè)頂點(diǎn)實(shí) 現(xiàn)的），判斷它的三條邊是否同色，如果同色則累加到總數(shù) R 中（當(dāng)然，初始時(shí) R 為 0）。 這個(gè)算法怎么樣呢？姑且不論它非常奢侈地需要一個(gè) 1M 的大數(shù)組（ POI97的時(shí)候還沒有大內(nèi)存），它的時(shí)間復(fù)雜度已經(jīng)高達(dá) O(C(n,3))，也就是 O(n3)的級(jí)別。對(duì)于 n 最大達(dá)到 1000 的本題來說，實(shí)在不能說是個(gè)好算法。 那些常規(guī)的技巧能不能用到本題上呢？離散化和極大化看起來跟本題毫不沾邊。由于本題的限制條件非常少，也不是求最值型的計(jì)數(shù)問題，所以二分和事件表看來也用不上。 看來，想要循規(guī)蹈矩地解決這題是不可能了，我們需要全新的思路！ 深入思考 稍稍進(jìn)一步分析就會(huì)發(fā)現(xiàn)，本題中單色三角形的個(gè)數(shù)將是非常多的，所以一切需要枚舉出每一個(gè)單色三角形的方法都是不可能高效的。 單純的枚舉不可以，那么組合計(jì)數(shù)是否可行呢？從總體上進(jìn)行組合計(jì)數(shù)很難圖一 想到，那么我們嘗試枚舉每一個(gè)點(diǎn)，設(shè)法找到一個(gè)組合公式來計(jì)算以這個(gè)點(diǎn)為頂點(diǎn)的單色三角形的個(gè)數(shù)。 這樣似乎已經(jīng)觸及到問題的本質(zhì)了，因?yàn)槔媒M合公式進(jìn)行計(jì)算是非常高效的。但是仔細(xì)分析后可以發(fā)現(xiàn)，這個(gè)組合公式是很難找到的，因?yàn)閷?duì)于枚舉確定的點(diǎn) A，以 A 為一個(gè)頂點(diǎn)的單色三角形 ABC 不僅要滿足邊 AB 和邊 AC 同色，而且邊 BC 也 要和 AB、 AC 邊同色，于是不可能僅僅通過枚舉一個(gè)頂點(diǎn) A 就可以確定單色三角形。 經(jīng)過上面的分析，我們得出枚舉＋組合計(jì)數(shù)有可能是正確的解法，但是在組合公式的構(gòu)造上我們遇到了障礙。這個(gè)障礙的本質(zhì)是： 從一個(gè)頂點(diǎn) A 出發(fā)的兩條同色的邊 AB、 AC 并不能確定一個(gè)單色三角形ABC，因?yàn)?BC 邊有可能不同色。 也就是說，我們無法在從同一個(gè)頂點(diǎn)出發(fā)的某兩條邊與所有的單色三角形之間建立一種確定的對(duì)應(yīng)關(guān)系。 補(bǔ)集轉(zhuǎn)化 讓我們換一個(gè)角度，從反面來看問題：因?yàn)槊績牲c(diǎn)都有邊連接，所以每三個(gè)點(diǎn)都可以組成一個(gè)三角形（單色或非單色的），那 么所有的三角形數(shù)S=C(n,3)=n*(n1)*(n2)/6。又因?yàn)閱紊切螖?shù) R 加上非單色三角形數(shù) T 就等于S，所以如果我們可以求出 T，那么顯然， R=S－ T。于是原問題就等價(jià)于：怎樣高效地求出 T。 純枚舉的算法想都不用想就被排除，那么在上面分析中夭折的枚舉＋組合計(jì)數(shù)的算法又怎樣呢？這個(gè)算法原先的障礙是無法在“某兩條邊”與“單色三角形”之間建立確定的對(duì)應(yīng)關(guān)系。那么有公共頂點(diǎn)的某兩條邊與非單色三角形之間是否有著確定的關(guān)系呢？對(duì)了！這種關(guān)系是明顯的： 非單色三角形的三條邊，共有紅黑兩種顏色，也就是說，只能是 兩條邊同色，另一條邊異色。假設(shè)同色的兩條邊頂點(diǎn)為 A，另外兩個(gè)頂點(diǎn)為 B 和 C，則從 B點(diǎn)一定引出兩條不同色的邊 BA 和 BC，同樣，從 C 點(diǎn)引出兩條不同色
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1