先交代一下背景。我拿到這道“HJ116 小紅的排列構(gòu)造②”的時(shí)候題面信息少得可憐關(guān)鍵詞就四個(gè)字排列構(gòu)造。做過(guò)?？蜕螲J系列、或者刷過(guò)“小紅”系列題的朋友應(yīng)該懂這類(lèi)題有個(gè)共同氣質(zhì)題面短、約束簡(jiǎn)單但留給你的思考空間極大。標(biāo)題里的“②”說(shuō)明前面還有一道①按這類(lèi)題的尿性①大概率是“構(gòu)造一個(gè)排列滿(mǎn)足某種簡(jiǎn)單性質(zhì)”②則是把性質(zhì)升級(jí)成“恰好滿(mǎn)足某個(gè)參數(shù)”。順著這個(gè)思路我這篇就把它當(dāng)成一個(gè)典型的排列構(gòu)造題來(lái)拆重點(diǎn)講清楚拿到這種只有一句話(huà)的題怎么從拆條件、猜無(wú)解、暴力找規(guī)律到最終寫(xiě)出一個(gè)能AC的構(gòu)造以及構(gòu)造完怎么證明、怎么自檢。這篇文章適合誰(shuí)看如果你刷構(gòu)造題經(jīng)?？ㄗ』蛘咭豢吹健罢?qǐng)你構(gòu)造一個(gè)排列”就只會(huì)寫(xiě)DFS回溯那這篇應(yīng)該能給你一套成體系的思考流程。我會(huì)用一個(gè)具體題面當(dāng)主線(xiàn)展開(kāi)最后再補(bǔ)三個(gè)常見(jiàn)的“②號(hào)升級(jí)方向”每個(gè)都配代碼和驗(yàn)證思路。1. 拆題把“構(gòu)造一個(gè)排列”變成可以操作的條件1.1 排列構(gòu)造題的第一性問(wèn)題“請(qǐng)構(gòu)造一個(gè)長(zhǎng)度為n的排列p滿(mǎn)足……”這種題本質(zhì)上只問(wèn)你一件事這n個(gè)數(shù)怎么擺。它不問(wèn)你方案數(shù)不用DP不是求最值不需要二分。你唯一要決定的是順序。所以拿到題的第一步不要急著想“我會(huì)不會(huì)做”而是先確認(rèn)三件事元素集合是固定的1到n每個(gè)數(shù)恰好出現(xiàn)一次。約束在相鄰關(guān)系上還是在全局關(guān)系上。如果給了參數(shù)kk的取值范圍決定有沒(méi)有無(wú)解的情況。以我們主線(xiàn)用的題面為例給定n和k構(gòu)造1~n的排列使得相鄰兩個(gè)數(shù)中“前者小于后者”的位置個(gè)數(shù)恰好為k。我先把這個(gè)叫“升沿?cái)?shù)”后面都這么叫。這類(lèi)約束的本質(zhì)就是你手里有n-1個(gè)相鄰對(duì)每個(gè)對(duì)要么是升沿要么是降沿升沿?cái)?shù)剛好k。換句話(huà)說(shuō)降沿?cái)?shù)等于n-1-k。一旦意識(shí)到這一點(diǎn)問(wèn)題就從“排列”變成了“設(shè)計(jì)一條有k次上坡、n-1-k次下坡的折線(xiàn)圖”。等下這個(gè)轉(zhuǎn)折很重要它能直接引導(dǎo)出構(gòu)造。1.2 把“恰好k個(gè)升沿”翻譯成結(jié)構(gòu)語(yǔ)言你可以在草稿紙上把排列畫(huà)成折線(xiàn)圖橫軸是位置縱軸是數(shù)值。相鄰兩個(gè)點(diǎn)后一個(gè)更高就是一個(gè)升沿計(jì)數(shù)器1后一個(gè)更低就是一個(gè)降沿計(jì)數(shù)器不變。要恰好k個(gè)升沿最容易想到的結(jié)構(gòu)是什么先往上爬k次然后一路往下。爬升階段貢獻(xiàn)升沿下坡階段不貢獻(xiàn)額外升沿。這不是唯一的合法結(jié)構(gòu)但它是最簡(jiǎn)單、最好證明的那類(lèi)結(jié)構(gòu)。構(gòu)造題里先找一個(gè)“足夠簡(jiǎn)單到能證明”的結(jié)構(gòu)往往比追求“最優(yōu)結(jié)構(gòu)”更重要。1.3 先判斷無(wú)解再想構(gòu)造這個(gè)題面里k的取值范圍是0到n-1理論覆蓋全部相鄰關(guān)系數(shù)。k0就是全降序kn-1就是全升序中間每個(gè)值都可達(dá)。所以這個(gè)版本沒(méi)有無(wú)解情況不需要輸出-1。這一點(diǎn)本身就是提示既然所有k都能構(gòu)造解法一定不復(fù)雜別把它想成難題。我自己的習(xí)慣是拿到參數(shù)先畫(huà)范圍。如果題目給的k在[0, n-1]區(qū)間內(nèi)說(shuō)明出題人沒(méi)想卡邊界直接找通項(xiàng)公式就行。如果k的合法取值中間有洞比如“k不能等于1”那才是真考點(diǎn)后面講環(huán)狀版本會(huì)碰到。2. 一個(gè)公式搞定所有k升段加斷點(diǎn)加降段2.1 構(gòu)造直覺(jué)為什么斷點(diǎn)要選最大的n繼續(xù)按折線(xiàn)圖的思路。我想要k個(gè)升沿就先把前面一段排成嚴(yán)格遞增比如[1, 2, 3, ..., k]這段內(nèi)部正好產(chǎn)生k-1個(gè)升沿。還差1個(gè)升沿怎么補(bǔ)把當(dāng)前最大的數(shù)n放到第k個(gè)數(shù)后面也就是排成[1, 2, 3, ..., k, n]。別忘了k肯定小于n除非kn-1所以k到n之間必然有一個(gè)升沿這就湊夠了第k個(gè)。接下來(lái)為了不再多產(chǎn)生升沿剩下所有數(shù)必須嚴(yán)格遞減并且遞減序列的起點(diǎn)恰好是n-1。由于1到k已經(jīng)被用了剩下的數(shù)是k1, k2, ..., n-1它們按降序排成[n-1, n-2, ..., k1]就行。所以完整的構(gòu)造是p [1, 2, ..., k] [n] [n-1, n-2, ..., k1]為什么斷點(diǎn)選最大的n而不是別的數(shù)很簡(jiǎn)單因?yàn)閚后面不管接誰(shuí)都是降沿n前面接k產(chǎn)生升沿。這個(gè)“前升后降”的結(jié)構(gòu)里n是天然的轉(zhuǎn)折點(diǎn)。2.2 用表格驗(yàn)證n7時(shí)所有k的構(gòu)造光說(shuō)不夠我拉一個(gè)n7的完整表格每個(gè)k對(duì)應(yīng)一個(gè)構(gòu)造序列和它的升沿?cái)?shù)方便你直接對(duì)照檢查。k構(gòu)造序列升沿位置說(shuō)明升沿總數(shù)0[7, 6, 5, 4, 3, 2, 1]全部降01[1, 7, 6, 5, 4, 3, 2]只有1712[1, 2, 7, 6, 5, 4, 3]12, 2723[1, 2, 3, 7, 6, 5, 4]12, 23, 3734[1, 2, 3, 4, 7, 6, 5]前三段加4745[1, 2, 3, 4, 5, 7, 6]前四段加5756[1, 2, 3, 4, 5, 6, 7]全部升6有沒(méi)有發(fā)現(xiàn)規(guī)律k每加1序列前面就多一個(gè)數(shù)字后面的降序段就短一格。這其實(shí)就是公式在干的事。2.3 證明這個(gè)構(gòu)造一定合法寫(xiě)構(gòu)造題最怕的是“樣例能過(guò)、全量超綱”。所以要養(yǎng)成習(xí)慣構(gòu)造完把合法性證明寫(xiě)清楚。這個(gè)構(gòu)造只需要證明三件事。第一每個(gè)數(shù)恰好出現(xiàn)一次。序列分三段前綴[1..k]用了1到k中間放了n后綴[n-1..k1]用了k1到n-1。三段集合互不重疊并起來(lái)正好是1到n。注意k0時(shí)前綴為空kn-1時(shí)后綴為空邊界同樣成立。第二升沿?cái)?shù)恰好為k。前綴[1..k]是嚴(yán)格遞增的內(nèi)部升沿k-1個(gè)。k和n之間因?yàn)閚一定大于k產(chǎn)生1個(gè)升沿。所以前面一共k個(gè)。后綴[n-1, n-2, ..., k1]嚴(yán)格遞減內(nèi)部0個(gè)升沿。n到n-1是降沿也不貢獻(xiàn)。合計(jì)就是k不多不少。第三k能取到全部合法值。k0時(shí)序列退化成純降序kn-1時(shí)退化成升序中間任意值都能由公式生成。證明完畢。這個(gè)證明雖然樸素但已經(jīng)是完整的三段論了。2.4 代碼實(shí)現(xiàn)Python和C兩個(gè)版本Python版本def build(n, k): p [] for i in range(1, k 1): p.append(i) p.append(n) for i in range(n - 1, k, -1): p.append(i) return p def check(p, k): n len(p) assert sorted(p) list(range(1, n 1)) cnt sum(1 for i in range(n - 1) if p[i] p[i 1]) assert cnt k, (p, cnt, k) for n in range(1, 10): for k in range(n): check(build(n, k), k) print(all tests passed)這段代碼里最容易寫(xiě)錯(cuò)的是第二個(gè)循環(huán)的邊界。range(n-1, k, -1)輸出的是n-1, n-2, ..., k1剛好不包含k因?yàn)閗已經(jīng)出現(xiàn)在前綴末尾了。如果你寫(xiě)成range(n-1, k-1, -1)就會(huì)把k重復(fù)放進(jìn)去元素就重復(fù)了。我用一個(gè)斷言函數(shù)把所有小規(guī)模都驗(yàn)了一遍n從1到9、k從0到n-1全部通過(guò)。C版本供OJ參考vectorint construct(int n, int k) { vectorint p; for (int i 1; i k; i) p.push_back(i); p.push_back(n); for (int i n - 1; i k; i--) p.push_back(i); return p; }順手提一個(gè)對(duì)稱(chēng)技巧如果題目改成“降沿恰好k個(gè)”不需要重想構(gòu)造直接把上面構(gòu)造里的每個(gè)數(shù)x換成n1-x升沿就全變降沿了反之亦然。這是排列里很常用的“鏡像補(bǔ)”操作。3. 加碼當(dāng)①變成②出題人最?lèi)?ài)加的三種約束題目編號(hào)既然帶個(gè)“②”說(shuō)明出題人不太可能讓你一個(gè)公式秒完。常見(jiàn)的升級(jí)方向我總結(jié)成三種每一種都能把一道基礎(chǔ)構(gòu)造題改出新考點(diǎn)。3.1 升級(jí)一要求字典序最小的合法構(gòu)造第一種升級(jí)是“輸出字典序最小的排列”。別慌我直接告訴你結(jié)論上面這個(gè)基礎(chǔ)構(gòu)造就是字典序最小的合法解。為什么用反證法推。任何合法排列第一位都是1嗎不一定比如n4、k1時(shí)[2,1,4,3]也是合法解第一位是2。但在“字典序最小”的競(jìng)爭(zhēng)里第一位顯然要優(yōu)先取最小的可用數(shù)。第一位放1一定能讓后續(xù)繼續(xù)湊出k個(gè)升沿因?yàn)榘鸦A(chǔ)構(gòu)造的第一位就是1說(shuō)明1開(kāi)頭可行所以任何第一位大于1的解字典序都不可能小于1開(kāi)頭的解。繼續(xù)看第二位。如果第一位是1第二位理論上可以放2到n中的任何一個(gè)。放2會(huì)讓字典序更小而且放2之后還能構(gòu)造出k個(gè)升沿基礎(chǔ)構(gòu)造就是例子。放更大數(shù)則字典序更大。所以第二位必須取2。同理推下去前k位只能是1, 2, 3, ..., k。第k1位呢基礎(chǔ)構(gòu)造放的是n。如果你在這里放一個(gè)比n小的數(shù)x那么x和前面的k構(gòu)成第k個(gè)升沿之后剩余的數(shù)里還有n。而n比任何剩余數(shù)都大n遲早要出現(xiàn)在某個(gè)位置它出現(xiàn)的那一步必然構(gòu)成一個(gè)升沿就會(huì)把總數(shù)頂?shù)絢1直接超了。所以第k1位只能是n。后面為了不再產(chǎn)生升沿必須嚴(yán)格遞減遞減的順序也就唯一了。結(jié)論就是這個(gè)構(gòu)造不僅合法而且已經(jīng)是字典序最小。這個(gè)結(jié)論很多題解不會(huì)專(zhuān)門(mén)寫(xiě)但如果你遇到“字典序最小”的題面可以直接用省得再寫(xiě)貪心。3.2 升級(jí)二相鄰差的絕對(duì)值必須互不相同第二種升級(jí)更經(jīng)典“構(gòu)造1到n的排列使得任意相鄰兩個(gè)數(shù)的差的絕對(duì)值互不相同?！边@個(gè)約束等價(jià)于相鄰差的絕對(duì)值正好覆蓋1到n-1。因?yàn)橐还瞡-1個(gè)相鄰對(duì)差的絕對(duì)值必須互不相同而差的范圍只有1到n-1所以只能是全覆蓋。這類(lèi)構(gòu)造有一個(gè)非常漂亮的“兩端交錯(cuò)”公式幾分鐘就能推出來(lái)。你想讓差值序列變成n-1, n-2, ..., 1那就讓相鄰元素從兩端交替取n 8: 1, 8, 2, 7, 3, 6, 4, 5差值7, 6, 5, 4, 3, 2, 1。完美。奇數(shù)個(gè)也一樣n 7: 1, 7, 2, 6, 3, 5, 4差值6, 5, 4, 3, 2, 1。驗(yàn)證一下最后一對(duì)5和4差1正好收尾。證明很簡(jiǎn)單排列里相鄰兩項(xiàng)總是“左指針的數(shù)、右指針的數(shù)”交替出現(xiàn)。每一次移動(dòng)左指針加1、右指針減1所以相鄰兩項(xiàng)之間的差恰好是當(dāng)前兩指針的距離而這個(gè)距離每走一步減少1。從n-1一路減到1沒(méi)有重復(fù)。代碼實(shí)現(xiàn)def build_diff(n): l, r 1, n p [] while l r: p.append(l) p.append(r) l 1 r - 1 if l r: p.append(l) return p def check_diff(p): n len(p) assert sorted(p) list(range(1, n 1)) diffs [abs(p[i] - p[i 1]) for i in range(n - 1)] assert len(diffs) len(set(diffs)) n - 1 for n in range(2, 20): check_diff(build_diff(n)) print(all diff tests passed)“兩端交錯(cuò)”這個(gè)模板在排列構(gòu)造里出現(xiàn)過(guò)無(wú)數(shù)次后面凡是遇到“相鄰元素差要覆蓋某個(gè)區(qū)間”的題優(yōu)先想它。3.3 升級(jí)三把序列首尾相接變成一個(gè)環(huán)第三種升級(jí)是把首尾也計(jì)入相鄰關(guān)系也就是環(huán)狀版本給定n和k構(gòu)造一個(gè)排列使得環(huán)上順時(shí)針相鄰的升沿?cái)?shù)恰好為k。這一下就把“所有k都可構(gòu)造”的結(jié)論打破了開(kāi)始有無(wú)解判斷了。先看基礎(chǔ)構(gòu)造在環(huán)狀下會(huì)變成什么。如果k0序列是純降序首尾是n和1n1所以首尾是降沿環(huán)形升沿總數(shù)還是0可行。如果k大于等于1基礎(chǔ)構(gòu)造的序列是[1, 2, ..., k, n, n-1, ..., k1]首尾分別是1和k1。注意k1至少是2所以1k1首尾必然構(gòu)成一個(gè)新的升沿。也就是說(shuō)線(xiàn)性構(gòu)造有k個(gè)升沿首尾接起來(lái)會(huì)多1個(gè)環(huán)形升沿?cái)?shù)變成k1。那么環(huán)形升沿?cái)?shù)s可以取哪些值s0可行s從2到n也都可以因?yàn)榱頺s-1k的范圍是1到n-1線(xiàn)性構(gòu)造后加上首尾一升正好s。唯獨(dú)s1不可行因?yàn)閟1要求線(xiàn)性k0且首尾升可線(xiàn)性k0是全降序首尾不可能升。所以結(jié)論是n大于等于3時(shí)s1無(wú)解其余s在0到n之間都有解。這里要小心一個(gè)邊界特例n2時(shí)排列[1,2]的環(huán)狀升沿是1排列[2,1]的環(huán)狀升沿是0所以s1反而有解。寫(xiě)代碼時(shí)如果題目數(shù)據(jù)范圍包含n2記得特判。這個(gè)“加起來(lái)多一環(huán)”的套路在很多環(huán)狀構(gòu)造題里都能用上本質(zhì)上就是讓你檢查首尾這一對(duì)額外貢獻(xiàn)了什么。3.4 三種升級(jí)的共同套路觀察一下你會(huì)發(fā)現(xiàn)出題人升級(jí)無(wú)非三種手段加參數(shù)、加邊界、加額外約束。加k是考參數(shù)化思維加字典序是考構(gòu)造唯一性證明加環(huán)是考邊界貢獻(xiàn)。但不管怎么加底層還是那個(gè)“升段斷點(diǎn)降段”或者“兩端交錯(cuò)”的模板。做題時(shí)先把基礎(chǔ)模板吃透再想升級(jí)在哪個(gè)環(huán)節(jié)動(dòng)了手腳。4. 先暴力再找規(guī)律構(gòu)造題還沒(méi)思路時(shí)的救命流程4.1 構(gòu)造不出來(lái)時(shí)DFS回溯是第一幫手有些構(gòu)造題你想了十分鐘毫無(wú)頭緒很正常。我的習(xí)慣是別硬想先寫(xiě)一個(gè)DFS把n比較小比如n≤8的所有合法排列全部枚舉出來(lái)人工看規(guī)律。下面是主線(xiàn)上這個(gè)題的暴搜代碼帶一點(diǎn)剪枝n8以下瞬間出結(jié)果def dfs_all_solutions(n, k): used [False] * (n 1) ans [] def dfs(cur, last, rises): if rises k: return # 剩余每個(gè)位置最多還能貢獻(xiàn)一個(gè)升沿如果不夠就直接剪 if rises (n - len(cur)) k: return if len(cur) n: if rises k: ans.append(cur[:]) return for x in range(1, n 1): if not used[x]: used[x] True cur.append(x) dfs(cur, x, rises (1 if x last else 0)) cur.pop() used[x] False dfs([], n 1, 0) return ans sols dfs_all_solutions(6, 2) print(len(sols)) for p in sols[:5]: print(p)調(diào)用時(shí)last傳n1這樣第一個(gè)數(shù)不會(huì)因?yàn)椤皒 last”被誤判成升沿因?yàn)樗泻蜻x數(shù)都小于n1。具體輸出我就不貼了你自己跑一下n6、k2的時(shí)候合法解數(shù)量已經(jīng)不少了。4.2 從全解列表里“看”出構(gòu)造拿到幾百個(gè)解怎么找規(guī)律我通常會(huì)提取每個(gè)解的“升降特征”把升記為0、降記為1然后掃描特征串。比如基礎(chǔ)構(gòu)造[1,2,3,7,6,5,4]的特征串就是00011。一列出來(lái)就能發(fā)現(xiàn)一個(gè)非常強(qiáng)的規(guī)律存在一族解的特征串是連續(xù)的0后面接連續(xù)的1而且0的個(gè)數(shù)正好和k有關(guān)。這直接提示你“前面升一段、后面降一段”是可行結(jié)構(gòu)然后順著這個(gè)思路去設(shè)計(jì)斷點(diǎn)公式就出來(lái)了。這個(gè)方法對(duì)絕大多數(shù)排列構(gòu)造題都適用不只是這一道。你如果經(jīng)常刷題應(yīng)該遇到過(guò)很多次“構(gòu)造不出來(lái)一暴力枚舉就看出答案”的情況。本質(zhì)原因是構(gòu)造題的合法解通常有很強(qiáng)的模式化特征而枚舉能把那個(gè)模式懟到你面前。4.3 給構(gòu)造代碼焊上驗(yàn)證函數(shù)我自己的習(xí)慣是任何構(gòu)造題寫(xiě)完第一版答案先不急著交本地用一個(gè)check函數(shù)把所有小規(guī)模數(shù)據(jù)全跑一遍。這個(gè)動(dòng)作花不了三十秒但能攔住九成以上的低級(jí)錯(cuò)誤。上面主線(xiàn)那個(gè)版本我寫(xiě)了兩個(gè)check一個(gè)驗(yàn)證元素集合、一個(gè)驗(yàn)證升沿計(jì)數(shù)然后把n1到9、k0到n-1的組合全跑了一遍全綠才敢提交。如果你在OJ上是手寫(xiě)題沒(méi)有本地環(huán)境至少也要在腦子里過(guò)一遍邊界n1、k0n2、k0和k1。5. 提交前最后五分鐘自查清單和翻車(chē)現(xiàn)場(chǎng)5.1 構(gòu)造題的四件套自查不管題目多簡(jiǎn)單提交前我固定檢查四件事元素完整性輸出是不是1到n每個(gè)恰好一次有沒(méi)有重復(fù)、有沒(méi)有遺漏約束滿(mǎn)足性把條件親自數(shù)一遍不是“看起來(lái)滿(mǎn)足”而是真按循環(huán)統(tǒng)計(jì)一遍。邊界情況n1、n2、k取最小值和最大值這三個(gè)點(diǎn)最容易無(wú)意識(shí)寫(xiě)錯(cuò)。輸出格式有沒(méi)有多打空格、漏了換行、數(shù)組下標(biāo)用的是0還是1。5.2 三個(gè)真實(shí)翻車(chē)案例第一個(gè)翻車(chē)是把“恰好k個(gè)”讀成“至少k個(gè)”。你知道嗎這種錯(cuò)誤用樣例測(cè)是測(cè)不出來(lái)的因?yàn)闃永ǔ＝o的k正好等于能產(chǎn)生的最大升沿?cái)?shù)附近你按“至少”構(gòu)造也能滿(mǎn)足樣例等數(shù)據(jù)里出現(xiàn)k比較小的case一下就WA了。所以審題時(shí)遇到“恰好”我會(huì)刻意在代碼里寫(xiě)一個(gè)嚴(yán)格相等的assert。第二個(gè)翻車(chē)是循環(huán)邊界。基礎(chǔ)構(gòu)造里range(n-1, k, -1)和range(n-1, k-1, -1)只差一個(gè)位置結(jié)果前者正確后者會(huì)讓k這個(gè)數(shù)字重復(fù)出現(xiàn)。這種問(wèn)題靠肉眼不容易看出來(lái)但靠check函數(shù)一秒就能抓到。第三個(gè)翻車(chē)是環(huán)狀版本里n2的特判。如果你套用“s1無(wú)解”的結(jié)論n2、s1時(shí)直接輸出-1就錯(cuò)了。所以每次總結(jié)出“無(wú)解結(jié)論”的時(shí)候我都會(huì)順手把最小n單獨(dú)驗(yàn)一遍習(xí)慣性踩點(diǎn)。5.3 關(guān)于排列構(gòu)造題的一點(diǎn)個(gè)人體會(huì)我刷排列構(gòu)造題最深的感受是這類(lèi)題不考高深算法考的是你把約束“翻譯”成結(jié)構(gòu)的能力。翻譯得好答案就是一個(gè)循環(huán)的事翻譯不好你會(huì)覺(jué)得出題人是在刁難你。分享幾個(gè)我常用的“構(gòu)造零件”升段加斷點(diǎn)加降段解決計(jì)數(shù)類(lèi)約束兩端交替解決差值覆蓋類(lèi)約束鏡像補(bǔ)數(shù)n1-x解決對(duì)稱(chēng)約束首尾檢查解決環(huán)狀約束。遇到新題時(shí)先對(duì)著這些零件看看有沒(méi)有能懟上的比從零開(kāi)始想省力得多。如果你也被構(gòu)造題卡過(guò)強(qiáng)烈建議下次先寫(xiě)個(gè)n≤8的暴力枚舉把合法解打出來(lái)看一眼。很多時(shí)候答案早就在你面前了你只是還沒(méi)發(fā)現(xiàn)它長(zhǎng)什么樣。