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