【正文】 及其特點(diǎn) ?什么叫構(gòu)造法： 直接列舉出滿足條件的對象或反例，導(dǎo)致結(jié)論的肯定與否定，間接構(gòu)造某種對應(yīng)關(guān)系，使問題根據(jù)需要進(jìn)行轉(zhuǎn)化的方法。 ? 設(shè)已經(jīng)構(gòu)造了 s個三元組（ x1,y1,z1)、（ x2,y2,z2)、 …… （ xs,ys,zs)，滿足 x1x2…… xs。 一旦 n、 x、 y的奇偶性確定，路線在邊界處的情況就可以唯一確定 IOI’ 2021冬令營講稿 例三：棋盤遍歷問題（ 3） ? n為奇數(shù) i. x、 y奇偶性相同，不妨設(shè) x、 y均為偶數(shù)，否則適當(dāng)?shù)匦D(zhuǎn)、翻轉(zhuǎn)棋盤 IOI’ 2021冬令營講稿 例三：棋盤遍歷問題（ 4） ? n為奇數(shù) ii. x、 y奇偶性不同，此時問題無解 先對棋盤進(jìn)行黑白二染色，如左圖 n為奇數(shù) ? 遍歷棋盤要走奇數(shù)步 ?終止點(diǎn)是黑格 x為奇數(shù) 、 y為偶數(shù) ?出發(fā)點(diǎn)是白格 ?黑格數(shù) =白格數(shù) n為奇數(shù) ?黑格數(shù) =白格數(shù) +1 ?矛盾 IOI’ 2021冬令營講稿 例三：小結(jié) 本題的分類并不是憑空得來的，而是基于 “ 迂回性折線 ” 的特點(diǎn)。 可以驗(yàn)證，這樣構(gòu)造出來的矩陣仍然滿足要求 1）、 2）、 3）、4）。 安排第一天的比賽如下： 設(shè) Aj是編號最小的負(fù)于對手的選手 ， 即 A A …… Aj1都取勝 ， Aj、Aj+ …… Ak都負(fù)于對手 。 加強(qiáng)命題是數(shù)學(xué)中一種常用的方法，在加強(qiáng)結(jié)論的同時，歸納假設(shè)的條件也增強(qiáng)了，為解題鋪平了道路。 上述命題仍然可以采用歸納構(gòu)造來解決。 Pm+1是一個 2m+1*2m+1的矩陣，啟發(fā)我們將它均分成四個 2m*2m的矩陣，實(shí)現(xiàn)從 Pm到 Pm+1的過渡。 分類構(gòu)造是分類的思想與構(gòu)造法相結(jié)合的產(chǎn)物 ， 簡單說來 ， 就是在分類的基礎(chǔ)上進(jìn)行構(gòu)造 。 ?取上面 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的位置。 ? 在熟悉的事物中尋找，在特殊的事物中尋找，接合目標(biāo)，不斷地調(diào)整甚至改變方案，直至實(shí)現(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） 之一 。 ??? ?niiii abl為奇數(shù)112) 取 [a2， b2]、 [a4， b4]、 [a6， b6]…… 這些編號為偶數(shù)的區(qū)間。它被頻繁采用并衍生出多種形式：如