算法合集之構(gòu)造——解題的最短路徑法(已修改)
2024-10-28 20:32 本頁面
【正文】 IOI’ 2021冬令營講稿 構(gòu)造 —— 解題的最短路徑 法 IOI’ 2021冬令營講稿 構(gòu)造法 —— 解題的 “ 最短路徑 ” ? 構(gòu)造法及其特點 ? 常用的構(gòu)造法 ? 構(gòu)造法的優(yōu)、缺點 Back IOI’ 2021冬令營講稿 構(gòu)造法及其特點 ?什么叫構(gòu)造法： 直接列舉出滿足條件的對象或反例，導(dǎo)致結(jié)論的肯定與否定，間接構(gòu)造某種對應(yīng)關(guān)系，使問題根據(jù)需要進行轉(zhuǎn)化的方法。 ?構(gòu)造法絕不是簡單的嘗試 ,也不是一時的運氣 ?構(gòu)造法使用的前提：存在性 ?構(gòu)造法特別適用于競賽中求單個可行解的題目 Back IOI’ 2021冬令營講稿 常用的構(gòu)造法 ? 直接構(gòu)造 ? 分類構(gòu)造 ? 歸納構(gòu)造 Back IOI’ 2021冬令營講稿 構(gòu)造法的優(yōu)、缺點 ? 優(yōu)點： 時空復(fù)雜度小，編程復(fù)雜度小 ? 缺點： 思維復(fù)雜度大 Back IOI’ 2021冬令營講稿 直接構(gòu)造 ? 一種直接對目標(biāo)對象進行考察的構(gòu)造方法。 ? 探索是直接構(gòu)造的靈魂，在構(gòu)造的背后，往往隱蔽著反反復(fù)復(fù)的嘗試。 ? 實際應(yīng)用中，首先對于目標(biāo)對象進行觀察，發(fā)現(xiàn)一般性的規(guī)律，加以概括總結(jié)后運用至構(gòu)造中。 ? 在熟悉的事物中尋找，在特殊的事物中尋找，接合目標(biāo)，不斷地調(diào)整甚至改變方案，直至實現(xiàn)構(gòu)造 IOI’ 2021冬令營講稿 例一：三臂起重機（ 1） 給出了三個數(shù) p、 q、 n， 要構(gòu)造若干個三元組 ， 符合以下四個要求： （ 1） 三元組必須具備形式 （ i， i+p， i+p+q） （ i， i+q，i+p+q） 之一 。 （ 2） 所有三元組中的元素不得超過 n+p+q。 （ 3） 1， 2， …… ， n+p+q這 n+p+q個數(shù)每個至多出現(xiàn)一次 。 （ 4） 這些三元組必須涵蓋 1， 2， …… ， n這 n個自然數(shù) 。 n≤ 300000， p+q≤ 60000。 IOI’ 2021冬令營講稿 例一：三臂起重機（ 2） 很自然想到構(gòu)造法。觀察以下幾個例子： p=1,q=1 (1,2,3) (4,5,6) (7,8,9) …… p=2,q=4 (1,3,7) (2,4,8) (5,9,11) (6,10,12) …… p=3,q=1 (1,4,5) (2,3,6) (7,10,11) …… p=1,q=3 (1,2,5) (3,4,7) (6,9,10) (8,11,12) …… 容易得出下面類似貪心的方法： ?設(shè)已經(jīng)構(gòu)造了 s個三元組（ x1,y1,z1)、（ x2,y2,z2)、 …… （ xs,ys,zs)，滿足 x1x2…… xs。 ?取上面 s個三元組中沒有出現(xiàn)過的最小自然數(shù) r +p沒有出現(xiàn)過 ? (xs+1,ys+1,zs+1)=(r,r+p,r+p+q) +p出現(xiàn)過 ? (xs+1,ys+1,zs+1)=(r,r+q,r+p+q) IOI’ 2021冬令營講稿 例一：三臂起重機（ 3） 這個方法馬上被下面的例子推翻： p=3,q=2 (1,4,6
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1