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