算法合集之淺談補(bǔ)集轉(zhuǎn)化思想在統(tǒng)計(jì)問題中的應(yīng)用-在線瀏覽
2025-02-26 09:23本頁面
【正文】 色三角形。例如圖一中有5 個(gè)點(diǎn)， 10 條邊，形成 3 個(gè)單色三角形。 3=n=1000， 0=m=250000。 這個(gè)算法怎么樣呢？姑且不論它非常奢侈地需要一個(gè) 1M 的大數(shù)組（ POI97的時(shí)候還沒有大內(nèi)存），它的時(shí)間復(fù)雜度已經(jīng)高達(dá) O(C(n,3))，也就是 O(n3)的級別。 那些常規(guī)的技巧能不能用到本題上呢？離散化和極大化看起來跟本題毫不沾邊。 看來，想要循規(guī)蹈矩地解決這題是不可能了，我們需要全新的思路！ 深入思考 稍稍進(jìn)一步分析就會(huì)發(fā)現(xiàn)，本題中單色三角形的個(gè)數(shù)將是非常多的，所以一切需要枚舉出每一個(gè)單色三角形的方法都是不可能高效的。 這樣似乎已經(jīng)觸及到問題的本質(zhì)了，因?yàn)槔媒M合公式進(jìn)行計(jì)算是非常高效的。 經(jīng)過上面的分析，我們得出枚舉＋組合計(jì)數(shù)有可能是正確的解法，但是在組合公式的構(gòu)造上我們遇到了障礙。 也就是說，我們無法在從同一個(gè)頂點(diǎn)出發(fā)的某兩條邊與所有的單色三角形之間建立一種確定的對應(yīng)關(guān)系。又因?yàn)閱紊切螖?shù) R 加上非單色三角形數(shù) T 就等于S，所以如果我們可以求出 T，那么顯然， R=S－ T。 純枚舉的算法想都不用想就被排除，那么在上面分析中夭折的枚舉＋組合計(jì)數(shù)的算法又怎樣呢？這個(gè)算法原先的障礙是無法在“某兩條邊”與“單色三角形”之間建立確定的對應(yīng)關(guān)系。假設(shè)同色的兩條邊頂點(diǎn)為 A，另外兩個(gè)頂點(diǎn)為 B 和 C，則從 B點(diǎn)一定引出兩條不同色的邊 BA 和 BC，同樣，從 C 點(diǎn)引出兩條不同色的邊 CA和 CB。 另一方面，如果從一個(gè)頂點(diǎn) B 引出兩條異色的邊 BA、 BC，則無論 AC 邊是何種顏色，三角形 ABC 都只能是一個(gè)非單色三角形。 很明顯，我們要求的非單色三角形數(shù) T 就等于所有“有公共頂點(diǎn)的異色邊”的總對數(shù) Q 的一半。枚舉頂點(diǎn)A，則根據(jù)乘法原理，以 A 為公共頂點(diǎn)的異色邊的對數(shù)就是 E[i]*(n1E[i])。這個(gè)算法的時(shí)間復(fù)雜度僅為 O(m+n)，空間復(fù)雜度是 O(n)，非常優(yōu)秀。這樣，就由單純的枚舉算法改為了枚舉 +組合計(jì)數(shù)的算法，大大降低了時(shí)間和空間復(fù)雜度。 例二 海戰(zhàn)游戲（改編自 Ural1212 Sea Battle） 題目大意 “海戰(zhàn)游戲”是在一個(gè) N 行 M 列的方格棋盤上擺放“軍艦”，一艘軍艦是連在一起的 X 行 Y 列方格，每個(gè)方格都全等于棋盤上的格子，于是軍艦就可以擺放在棋盤上，使軍艦的每個(gè)格子和棋盤的格子重合?，F(xiàn)在已經(jīng)擺放了 L 艘軍艦（符合擺放的規(guī)則），下一步想要再擺放一個(gè) P 行 Q 列的軍艦，求出共有多少種不同的可能擺放方案。其中 2=N,M=30000，0=L=30， 1=P,Q=5。 例如圖五中已經(jīng)擺放了一個(gè) 1 行 2 列的軍艦和一個(gè) 2 行 1 列的軍艦，如果我們要再擺一個(gè) 1 行 2 列的軍艦，有兩種方案。 初步分析 枚舉每一種擺放方式，再分別進(jìn)行判斷是否符合規(guī)則的方法顯然是不行的，因?yàn)樾枰杜e的擺放方式已經(jīng)在 O(N*M)的級別，更不要說還需要嵌套一個(gè)判斷的過程了。這是一種典型的在有障礙點(diǎn)的網(wǎng)格上求擺放方案數(shù)的統(tǒng)計(jì)問題。由于這不是本文的討論內(nèi)容，所以我們不多做研究，只給出初步的結(jié)論是：離散化的算法時(shí)間復(fù)雜度為 O((M+N)*L)，雖然對于原題勉強(qiáng)可以應(yīng)付，但是一旦數(shù)據(jù)規(guī)模再稍稍擴(kuò)大一點(diǎn)，必定超時(shí)。 如果想要圓滿地解決這道題，我們需要尋找新的算法。 ? 在一個(gè) X 行 Y 列的矩形 A 中放入一個(gè) P 行 Q 列的矩形 B，共有多少種擺放方案？ 結(jié)論一 ：矩形 B 能夠放入矩形 A 中的充要條件是 X=P 且 Y=Q，所以如果XP 或 YQ，方案數(shù)為 0。
試題試卷相關(guān)推薦
鄂ICP備17016276號-1