先交代一下背景。我拿到这道“HJ116 小红的排列构造②”的时候题面信息少得可怜关键词就四个字排列构造。做过牛客上HJ系列、或者刷过“小红”系列题的朋友应该懂这类题有个共同气质题面短、约束简单但留给你的思考空间极大。标题里的“②”说明前面还有一道①按这类题的尿性①大概率是“构造一个排列满足某种简单性质”②则是把性质升级成“恰好满足某个参数”。顺着这个思路我这篇就把它当成一个典型的排列构造题来拆重点讲清楚拿到这种只有一句话的题怎么从拆条件、猜无解、暴力找规律到最终写出一个能AC的构造以及构造完怎么证明、怎么自检。这篇文章适合谁看如果你刷构造题经常卡住或者一看到“请你构造一个排列”就只会写DFS回溯那这篇应该能给你一套成体系的思考流程。我会用一个具体题面当主线展开最后再补三个常见的“②号升级方向”每个都配代码和验证思路。1. 拆题把“构造一个排列”变成可以操作的条件1.1 排列构造题的第一性问题“请构造一个长度为n的排列p满足……”这种题本质上只问你一件事这n个数怎么摆。它不问你方案数不用DP不是求最值不需要二分。你唯一要决定的是顺序。所以拿到题的第一步不要急着想“我会不会做”而是先确认三件事元素集合是固定的1到n每个数恰好出现一次。约束在相邻关系上还是在全局关系上。如果给了参数kk的取值范围决定有没有无解的情况。以我们主线用的题面为例给定n和k构造1~n的排列使得相邻两个数中“前者小于后者”的位置个数恰好为k。我先把这个叫“升沿数”后面都这么叫。这类约束的本质就是你手里有n-1个相邻对每个对要么是升沿要么是降沿升沿数刚好k。换句话说降沿数等于n-1-k。一旦意识到这一点问题就从“排列”变成了“设计一条有k次上坡、n-1-k次下坡的折线图”。等下这个转折很重要它能直接引导出构造。1.2 把“恰好k个升沿”翻译成结构语言你可以在草稿纸上把排列画成折线图横轴是位置纵轴是数值。相邻两个点后一个更高就是一个升沿计数器1后一个更低就是一个降沿计数器不变。要恰好k个升沿最容易想到的结构是什么先往上爬k次然后一路往下。爬升阶段贡献升沿下坡阶段不贡献额外升沿。这不是唯一的合法结构但它是最简单、最好证明的那类结构。构造题里先找一个“足够简单到能证明”的结构往往比追求“最优结构”更重要。1.3 先判断无解再想构造这个题面里k的取值范围是0到n-1理论覆盖全部相邻关系数。k0就是全降序kn-1就是全升序中间每个值都可达。所以这个版本没有无解情况不需要输出-1。这一点本身就是提示既然所有k都能构造解法一定不复杂别把它想成难题。我自己的习惯是拿到参数先画范围。如果题目给的k在[0, n-1]区间内说明出题人没想卡边界直接找通项公式就行。如果k的合法取值中间有洞比如“k不能等于1”那才是真考点后面讲环状版本会碰到。2. 一个公式搞定所有k升段加断点加降段2.1 构造直觉为什么断点要选最大的n继续按折线图的思路。我想要k个升沿就先把前面一段排成严格递增比如[1, 2, 3, ..., k]这段内部正好产生k-1个升沿。还差1个升沿怎么补把当前最大的数n放到第k个数后面也就是排成[1, 2, 3, ..., k, n]。别忘了k肯定小于n除非kn-1所以k到n之间必然有一个升沿这就凑够了第k个。接下来为了不再多产生升沿剩下所有数必须严格递减并且递减序列的起点恰好是n-1。由于1到k已经被用了剩下的数是k1, k2, ..., n-1它们按降序排成[n-1, n-2, ..., k1]就行。所以完整的构造是p [1, 2, ..., k] [n] [n-1, n-2, ..., k1]为什么断点选最大的n而不是别的数很简单因为n后面不管接谁都是降沿n前面接k产生升沿。这个“前升后降”的结构里n是天然的转折点。2.2 用表格验证n7时所有k的构造光说不够我拉一个n7的完整表格每个k对应一个构造序列和它的升沿数方便你直接对照检查。k构造序列升沿位置说明升沿总数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有没有发现规律k每加1序列前面就多一个数字后面的降序段就短一格。这其实就是公式在干的事。2.3 证明这个构造一定合法写构造题最怕的是“样例能过、全量超纲”。所以要养成习惯构造完把合法性证明写清楚。这个构造只需要证明三件事。第一每个数恰好出现一次。序列分三段前缀[1..k]用了1到k中间放了n后缀[n-1..k1]用了k1到n-1。三段集合互不重叠并起来正好是1到n。注意k0时前缀为空kn-1时后缀为空边界同样成立。第二升沿数恰好为k。前缀[1..k]是严格递增的内部升沿k-1个。k和n之间因为n一定大于k产生1个升沿。所以前面一共k个。后缀[n-1, n-2, ..., k1]严格递减内部0个升沿。n到n-1是降沿也不贡献。合计就是k不多不少。第三k能取到全部合法值。k0时序列退化成纯降序kn-1时退化成升序中间任意值都能由公式生成。证明完毕。这个证明虽然朴素但已经是完整的三段论了。2.4 代码实现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)这段代码里最容易写错的是第二个循环的边界。range(n-1, k, -1)输出的是n-1, n-2, ..., k1刚好不包含k因为k已经出现在前缀末尾了。如果你写成range(n-1, k-1, -1)就会把k重复放进去元素就重复了。我用一个断言函数把所有小规模都验了一遍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个”不需要重想构造直接把上面构造里的每个数x换成n1-x升沿就全变降沿了反之亦然。这是排列里很常用的“镜像补”操作。3. 加码当①变成②出题人最爱加的三种约束题目编号既然带个“②”说明出题人不太可能让你一个公式秒完。常见的升级方向我总结成三种每一种都能把一道基础构造题改出新考点。3.1 升级一要求字典序最小的合法构造第一种升级是“输出字典序最小的排列”。别慌我直接告诉你结论上面这个基础构造就是字典序最小的合法解。为什么用反证法推。任何合法排列第一位都是1吗不一定比如n4、k1时[2,1,4,3]也是合法解第一位是2。但在“字典序最小”的竞争里第一位显然要优先取最小的可用数。第一位放1一定能让后续继续凑出k个升沿因为把基础构造的第一位就是1说明1开头可行所以任何第一位大于1的解字典序都不可能小于1开头的解。继续看第二位。如果第一位是1第二位理论上可以放2到n中的任何一个。放2会让字典序更小而且放2之后还能构造出k个升沿基础构造就是例子。放更大数则字典序更大。所以第二位必须取2。同理推下去前k位只能是1, 2, 3, ..., k。第k1位呢基础构造放的是n。如果你在这里放一个比n小的数x那么x和前面的k构成第k个升沿之后剩余的数里还有n。而n比任何剩余数都大n迟早要出现在某个位置它出现的那一步必然构成一个升沿就会把总数顶到k1直接超了。所以第k1位只能是n。后面为了不再产生升沿必须严格递减递减的顺序也就唯一了。结论就是这个构造不仅合法而且已经是字典序最小。这个结论很多题解不会专门写但如果你遇到“字典序最小”的题面可以直接用省得再写贪心。3.2 升级二相邻差的绝对值必须互不相同第二种升级更经典“构造1到n的排列使得任意相邻两个数的差的绝对值互不相同。”这个约束等价于相邻差的绝对值正好覆盖1到n-1。因为一共n-1个相邻对差的绝对值必须互不相同而差的范围只有1到n-1所以只能是全覆盖。这类构造有一个非常漂亮的“两端交错”公式几分钟就能推出来。你想让差值序列变成n-1, n-2, ..., 1那就让相邻元素从两端交替取n 8: 1, 8, 2, 7, 3, 6, 4, 5差值7, 6, 5, 4, 3, 2, 1。完美。奇数个也一样n 7: 1, 7, 2, 6, 3, 5, 4差值6, 5, 4, 3, 2, 1。验证一下最后一对5和4差1正好收尾。证明很简单排列里相邻两项总是“左指针的数、右指针的数”交替出现。每一次移动左指针加1、右指针减1所以相邻两项之间的差恰好是当前两指针的距离而这个距离每走一步减少1。从n-1一路减到1没有重复。代码实现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)“两端交错”这个模板在排列构造里出现过无数次后面凡是遇到“相邻元素差要覆盖某个区间”的题优先想它。3.3 升级三把序列首尾相接变成一个环第三种升级是把首尾也计入相邻关系也就是环状版本给定n和k构造一个排列使得环上顺时针相邻的升沿数恰好为k。这一下就把“所有k都可构造”的结论打破了开始有无解判断了。先看基础构造在环状下会变成什么。如果k0序列是纯降序首尾是n和1n1所以首尾是降沿环形升沿总数还是0可行。如果k大于等于1基础构造的序列是[1, 2, ..., k, n, n-1, ..., k1]首尾分别是1和k1。注意k1至少是2所以1k1首尾必然构成一个新的升沿。也就是说线性构造有k个升沿首尾接起来会多1个环形升沿数变成k1。那么环形升沿数s可以取哪些值s0可行s从2到n也都可以因为令ks-1k的范围是1到n-1线性构造后加上首尾一升正好s。唯独s1不可行因为s1要求线性k0且首尾升可线性k0是全降序首尾不可能升。所以结论是n大于等于3时s1无解其余s在0到n之间都有解。这里要小心一个边界特例n2时排列[1,2]的环状升沿是1排列[2,1]的环状升沿是0所以s1反而有解。写代码时如果题目数据范围包含n2记得特判。这个“加起来多一环”的套路在很多环状构造题里都能用上本质上就是让你检查首尾这一对额外贡献了什么。3.4 三种升级的共同套路观察一下你会发现出题人升级无非三种手段加参数、加边界、加额外约束。加k是考参数化思维加字典序是考构造唯一性证明加环是考边界贡献。但不管怎么加底层还是那个“升段断点降段”或者“两端交错”的模板。做题时先把基础模板吃透再想升级在哪个环节动了手脚。4. 先暴力再找规律构造题还没思路时的救命流程4.1 构造不出来时DFS回溯是第一帮手有些构造题你想了十分钟毫无头绪很正常。我的习惯是别硬想先写一个DFS把n比较小比如n≤8的所有合法排列全部枚举出来人工看规律。下面是主线上这个题的暴搜代码带一点剪枝n8以下瞬间出结果def dfs_all_solutions(n, k): used [False] * (n 1) ans [] def dfs(cur, last, rises): if rises k: return # 剩余每个位置最多还能贡献一个升沿如果不够就直接剪 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)调用时last传n1这样第一个数不会因为“x last”被误判成升沿因为所有候选数都小于n1。具体输出我就不贴了你自己跑一下n6、k2的时候合法解数量已经不少了。4.2 从全解列表里“看”出构造拿到几百个解怎么找规律我通常会提取每个解的“升降特征”把升记为0、降记为1然后扫描特征串。比如基础构造[1,2,3,7,6,5,4]的特征串就是00011。一列出来就能发现一个非常强的规律存在一族解的特征串是连续的0后面接连续的1而且0的个数正好和k有关。这直接提示你“前面升一段、后面降一段”是可行结构然后顺着这个思路去设计断点公式就出来了。这个方法对绝大多数排列构造题都适用不只是这一道。你如果经常刷题应该遇到过很多次“构造不出来一暴力枚举就看出答案”的情况。本质原因是构造题的合法解通常有很强的模式化特征而枚举能把那个模式怼到你面前。4.3 给构造代码焊上验证函数我自己的习惯是任何构造题写完第一版答案先不急着交本地用一个check函数把所有小规模数据全跑一遍。这个动作花不了三十秒但能拦住九成以上的低级错误。上面主线那个版本我写了两个check一个验证元素集合、一个验证升沿计数然后把n1到9、k0到n-1的组合全跑了一遍全绿才敢提交。如果你在OJ上是手写题没有本地环境至少也要在脑子里过一遍边界n1、k0n2、k0和k1。5. 提交前最后五分钟自查清单和翻车现场5.1 构造题的四件套自查不管题目多简单提交前我固定检查四件事元素完整性输出是不是1到n每个恰好一次有没有重复、有没有遗漏约束满足性把条件亲自数一遍不是“看起来满足”而是真按循环统计一遍。边界情况n1、n2、k取最小值和最大值这三个点最容易无意识写错。输出格式有没有多打空格、漏了换行、数组下标用的是0还是1。5.2 三个真实翻车案例第一个翻车是把“恰好k个”读成“至少k个”。你知道吗这种错误用样例测是测不出来的因为样例通常给的k正好等于能产生的最大升沿数附近你按“至少”构造也能满足样例等数据里出现k比较小的case一下就WA了。所以审题时遇到“恰好”我会刻意在代码里写一个严格相等的assert。第二个翻车是循环边界。基础构造里range(n-1, k, -1)和range(n-1, k-1, -1)只差一个位置结果前者正确后者会让k这个数字重复出现。这种问题靠肉眼不容易看出来但靠check函数一秒就能抓到。第三个翻车是环状版本里n2的特判。如果你套用“s1无解”的结论n2、s1时直接输出-1就错了。所以每次总结出“无解结论”的时候我都会顺手把最小n单独验一遍习惯性踩点。5.3 关于排列构造题的一点个人体会我刷排列构造题最深的感受是这类题不考高深算法考的是你把约束“翻译”成结构的能力。翻译得好答案就是一个循环的事翻译不好你会觉得出题人是在刁难你。分享几个我常用的“构造零件”升段加断点加降段解决计数类约束两端交替解决差值覆盖类约束镜像补数n1-x解决对称约束首尾检查解决环状约束。遇到新题时先对着这些零件看看有没有能怼上的比从零开始想省力得多。如果你也被构造题卡过强烈建议下次先写个n≤8的暴力枚举把合法解打出来看一眼。很多时候答案早就在你面前了你只是还没发现它长什么样。