算法合集之構(gòu)造——解題的最短路徑法-wenkub
2022-10-31 20:32:11 本頁面
【正文】 2， b2a4b3， …… ， bn2anbn1 IOI’ 2021冬令營講稿 例二：區(qū)間染色問題（ 3） 1) 取 [a1， b1]、 [a3， b3]、 [a5， b5]…… 這些編號為奇數(shù)的區(qū)間。 ? 設(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冬令營講稿 例一：三臂起重機(jī)（ 3） 這個方法馬上被下面的例子推翻： p=3,q=2 (1,4,6) (2,5,7) (3,?,8) ?處無論填 5還是6均已出現(xiàn)過 但是如果換一種填法： p=2,q=3 (1,3,6) (2,4,7) (5,8,10) (9,11,14) …… 交換一下 p、 q的位置，再應(yīng)用上面的填法 啟發(fā)我們，應(yīng)用上述填法的條件是： p≤q ，即當(dāng) pq時，先交換 p、 q的位置。 （ 4） 這些三元組必須涵蓋 1， 2， …… ， n這 n個自然數(shù) 。 ? 實際應(yīng)用中，首先對于目標(biāo)對象進(jìn)行觀察，發(fā)現(xiàn)一般性的規(guī)律，加以概括總結(jié)后運(yùn)用至構(gòu)造中。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ù)需要進(jìn)行轉(zhuǎn)化的方法。 ? 在熟悉的事物中尋找，在特殊的事物中尋找，接合目標(biāo)，不斷地調(diào)整甚至改變方案，直至實現(xiàn)構(gòu)造 IOI’ 2021冬令營講稿 例一：三臂起重機(jī)（ 1） 給出了三個數(shù) p、 q、 n， 要構(gòu)造若干個三元組 ， 符合以下四個要求： （ 1） 三元組必須具備形式 （ i， i+p， i+p+q） （ i， i+q，i+p+q） 之一 。 n≤ 300000， p+q≤ 60000。這僅僅是一個猜想，需要經(jīng)過實踐以及證明。 ? 取上面 s個三元組中沒有出現(xiàn)過的最小自然數(shù) r 1. r+p沒有出現(xiàn)過 ? (xs+1,ys+1,zs+1)=(r,r+p,r+p+q) 2. r+p出現(xiàn)過 ? (xs+1,ys+1,zs+1)=(r,r+q,r+p+q) ?從題面上看來， p、 q的位置應(yīng)當(dāng)是對稱的，為什么會需要假設(shè) “ p≤q ” 的情況呢？ IOI’ 2021冬令營講稿 例一：三臂起重機(jī)（ 5） 證明：若 r+p出現(xiàn)過，那么 r+q必定未出現(xiàn)。 ??? ?niiii abl為奇數(shù)112) 取 [a2， b2]、 [a4， b4]、 [a6， b6]…… 這些編號為偶數(shù)的區(qū)間。 對于某些題目，很難直接給出一種 “ 必
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1