上周打牛客练习赛第150场C题“乘鲨破浪”让我在草稿纸上画了快二十分钟。这题第一眼看上去很唬人题面短限制宽输出任意解——典型的构造题套路。构造题就是这样读题一时爽动手火葬场但一旦想通那个关键的数学结构代码量可能不到二十行。这篇文章我就把从读题、试错、证明到AC的完整思考链拆开讲再把构造题最常用的方法论一起沉淀出来给同样在刷牛客练习赛的朋友一个可直接参考的复盘模板。先说结论这道题的核心是让你构造一个排列使相邻元素的差的绝对值两两不同。由于是输出任意解所以不需要求最优化重点在于怎么稳定、快速地构造出合法方案。如果你也是一上赛场就讨厌构造题的人这篇文章应该能帮你把“瞎猜规律”变成“有章法地构造”。1. 赛题还原题目到底在考什么1.1 还原后的题面与特征分析牛客练习赛150C的题目原型以我赛后翻题解的记忆大致是这样的给定一个正整数n要求构造一个长度为n的排列p使得任意两个相邻位置的差的绝对值互不相同。也就是说集合{|p[1]-p[2]|, |p[2]-p[3]|, ..., |p[n-1]-p[n]|}中恰好包含n-1个不同的正整数。数据范围我记得大概是n≤2e5所以O(n)或O(n log n)的解法都可行但答案要求输出整个排列。拿到这种题先别急着写代码。构造题有个很实用的判断标准如果题目要求“输出任意一组可行解”而且限制条件看起来有很强的数学对称性那大概率不是让你去搜而是让你找一个闭式构造。这道题的特征就很典型——排列、相邻差、互不相同三个关键词拆开看都很简单合在一起就需要一点观察力了。1.2 为什么优先往“相邻差互不相同”方向想如果题目要你输出一个排列常用的构造思路有两种第一种是从小到大硬排第二种是人为制造某种规律。直接1,2,3,...,n排下去相邻差全是1显然不行。那能不能让相邻差恰好覆盖1到n-1这是最漂亮的状态因为n-1个相邻位置刚好对应n-1种差如果能做到每个差出现一次就直接满足要求了。这个“上界”想法非常关键。很多时候构造题不是让你凭空造一个答案而是让你最大化利用条件给出的每个数值位。差值的可能范围是1到n-1一共n-1种序列又有n-1对相邻元素所以“每种差值都出现一次”是一个足够自然的目标。一旦目标明确了构造方向就清晰了让差值序列变成n-1, n-2, ..., 1像倒数的波浪一样递减下去。1.3 构造题通用第一步暴力枚举找感觉我还记得赛时我做的第一件事不是硬推公式而是先在草稿纸上手算小n。n3时1,3,2的相邻差是2和1合法n4时1,4,2,3的相邻差是3,2,1合法n5时1,5,2,4,3的相邻差是4,3,2,1也合法。这几个例子一列出来规律几乎是跳到我脸上的左端取小数右端取大数交替进行。这就是构造题最重要的实操技巧之一先用小数据暴力枚举或手算找到可行解的共同模式再尝试证明这个模式为什么永远成立。直接推公式容易卡住但小数据会给你很强的直觉线索。2. 核心构造从两端交替取值差集自然铺满2.1 构造序列的直观过程前文已经提到对n5合法排列是1,5,2,4,3。仔细看这个过程第一个数取最小的1第二个数取最大的5第三个数取剩下的最小数2第四个数取剩下的最大数4最后剩下3。也就是说用两个指针l和r分别指向当前未取数的最小值和最大值每次交替取l和r向中间靠拢。写成序列就是 p 1, n, 2, n-1, 3, n-2, ...这个构造有个好处不需要额外的判断只需要知道当前是奇数位还是偶数位。奇数位取左边递增的小数序列1,2,3,...偶数位取右边递减的大数序列n,n-1,n-2,...。两边的数在中间相遇恰好用完1到n的所有数。2.2 差值序列为什么一定两两不同这是整道题的核心证明赛场上必须能在几十秒内说服自己。我们看相邻的两项|p[1]-p[2]| |1-n| n-1 |p[2]-p[3]| |n-2| n-2 |p[3]-p[4]| |2-(n-1)| n-3 |p[4]-p[5]| |(n-1)-3| n-4每往后走一步差值刚好减1。原因很简单两个指针l和r之间的距离每经过一对元素就缩小1所以相邻两项的差就是从n-1开始递减到1的等差数列。用数学归纳法也可以证明初始时区间是[1,n]长度是n先取左端1和右端n它们之间隔了n-1个整数差的绝对值就是n-1接着区间变成[2,n-1]长度是n-2左端2和右端n-1的差就是n-2以此类推直到最后。因为每一对差值都来自不同长度的区间数值天然不可能重复所以一定恰好覆盖1到n-1。2.3 代码实现从公式到三种写法最直接的实现是公式法遍历i从1到n如果i是奇数输出(i1)/2如果i是偶数输出n - i/2 1。这种写法的好处是空间O(1)适合n特别大的情况。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { if (i 1) { cout (i 1) / 2 ; } else { cout n - i / 2 1 ; } } cout \n; return 0; }如果觉得公式法不够直观也可以用双指针构造数组int l 1, r n; for (int i 0; i n; i) { if (i % 2 0) p[i] l; else p[i] r--; }两种写法的本质完全一样只是前者省去了存储后者更贴近“两个指针向中间靠拢”的直觉。我个人做构造题时一般先用双指针确认逻辑再在最终提交时改成公式法减少空间占用。2.4 边界情况n1和n2别掉坑很多构造题的正确性不是错在大数据而是错在小边界。n1时只有一个元素没有相邻位置题目条件自动满足直接输出1即可。n2时只有一对相邻差差的绝对值是1也自动满足输出1 2或2 1都行。用上面的公式法跑一遍n1时i1是奇数输出1没问题。n2时i1输出1i2输出2-112也没问题。所以公式法天然覆盖了这两个边界但如果你用双指针法也要注意循环里别在n1时访问p[1]。3. “乘”字变式从差到积的构造推广3.1 如果题目把“差”改成“积”从哪里切入题目叫“乘鲨破浪”一开始我还在想是不是跟乘法有关后来确认核心是相邻差的构造。但赛后我确实认真想过一个问题如果构造条件改成“相邻两项的乘积互不相同”同样的两端取数法还成立吗我快速验证了一下n6的情况按1,6,2,5,3,4排列相邻乘积是6,12,10,15,12——出现了重复的12。这说明两端交替取数只能解决差值的构造不能直接套用到乘积条件上。不过这个反例给了我们另一个启发构造题中每个条件都需要单独设计构造方案不能因为一个方法在某类题上漂亮就默认它能通吃所有变式。如果真遇到乘积互异类题目我建议先写一个DFS暴力把n1到n8的可行解全部打出来然后观察模式。例如n3时排列2,1,3的乘积是2和3互异n4时排列2,4,1,3的乘积是8,4,3也互异。这类打表工作能快速告诉你是否存在普适构造。3.2 经典的“波浪排列”变式与相邻差构造同样经典的另一类变式是要求排列满足a1 a3 ...也就是常见的wiggle排序。“乘鲨破浪”这个题名很容易让人联想到波浪所以我很自然地把这类变式也归到同一篇笔记里。波浪排列有一个非常简明的构造方案先把原数组排序然后把较小的前一半放到奇数下标较大的后一半放到偶数下标。因为后半段的每个数都大于前半段的每个数所以a1 a3 ...这个大小关系天然成立。牛客上不少构造题其实就是这类基础变形的组合掌握一个母题的构造方法后可以通过调整取值策略来解决多个变体。3.3 同类构造母题的常见套路盘点刷得多了会发现牛客练习赛里的构造题大多围绕几个母题展开排列类构造本题就是、区间覆盖类构造、模运算类构造、以及图论/网格类构造。排列类最常见的招数就是双端交替、奇偶分组、按值域分块。区间覆盖类通常要求你构造若干区间使每个点被覆盖次数满足某个条件这时优先想差分思想和递增序列。模运算类则常常依赖中国剩余定理或循环节来铺满值域。对这些母题最有效的训练方式是归类整理而不是一题一题孤立地刷。每次AC一道构造题后问自己这题如果改一个条件还能不能构造如果改成相反条件反例是什么这些问题比单纯刷题更能锻炼构造思维。4. 实操复盘从读题到AC的完整流程4.1 赛时手推过程还原下面还原一下我赛时的真实操作。开题看到构造题我先确定了三个信息目标是排列、限制是相邻差互不相同、数据范围大约2e5。接着我在草稿纸上写了几个小n的合法排列n3取1 3 2n4取1 4 2 3n5取1 5 2 4 3。这几个结果一出来我立刻意识到是左右交替。但我没有马上写代码而是先试着证明为什么左右交替一定合法。因为如果只是靠小数据猜规律万一n6的时候出问题就会在调试上浪费很多时间。我快速在草稿纸上验证了n6的排列1,6,2,5,3,4相邻差是5,4,3,2,1全部不同。到这一步我才确认规律成立然后才开始写代码。4.2 完整AC代码与逐段注释下面这段C17代码是我在赛场上提交的版本只保留核心逻辑去掉无关输出后也就十几行#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { // 奇数位输出左侧递增序列1, 2, 3, ... // 偶数位输出右侧递减序列n, n-1, n-2, ... if (i 1) { cout (i 1) / 2 ; } else { cout n - i / 2 1 ; } } return 0; }这里的(i1)/2在i为奇数时得到1,2,3,...n - i/2 1在i为偶数时得到n,n-1,n-2,...。两个分支交替输出整个排列就是一个完整的左右夹逼序列。不需要数组不需要额外的变量空间复杂度是O(1)。4.3 复杂度分析与性能对比时间上遍历一次n每个位置只做常数次运算所以时间复杂度是O(n)。空间上如果不存储数组只做输出就是O(1)。n最大2e5时输出本身才是主要瓶颈所以一定要关闭cin/cout同步流或者直接用printf/puts批量输出否则容易卡在IO上。对比双指针构造数组的写法公式法节省了一次完整的数组写回过程。虽然现代内存和CPU都很强2e5的数组开销几乎可以忽略但构造题养成分段输出、边构造边输出的习惯对后续做更大数据范围比如n1e6的题很有帮助。4.4 用对拍脚本验证构造正确性赛场上不能对拍但赛后复盘时我建议一定写一个checker脚本用Python验证所有n从1到100的构造结果是否合法。这能有效防止公式中奇偶写反等低级错误。import subprocess def check(n): # 假设C程序读取n并输出排列 out subprocess.check_output([./a.out], inputstr(n).encode()).decode().strip() p list(map(int, out.split())) assert sorted(p) list(range(1, n 1)), f{n}: 不是合法排列 diffs [abs(p[i] - p[i 1]) for i in range(n - 1)] assert len(set(diffs)) n - 1, f{n}: 差值重复 {diffs} print(fn{n}: OK) for n in range(1, 101): check(n)这是我做构造题必用的工具。很多看似正确的构造恰恰会在n2、n4这种小边界上暴露出奇偶下标错位的问题而暴力对拍能在一分钟内把所有小数据全部验证一遍比自己肉眼检查可靠得多。5. 常见问题与排查技巧实录5.1 相邻差出现重复的构造顺序误区我在练习时试过另一种构造顺序先取大数再取小数也就是n,1,n-1,2,...。这个序列的相邻差同样会从n-1递减到1所以也是合法的。但如果有人写成1,2,n,3,n-1,...这种“左端连续取两个小数再跳回右端”的顺序差值序列就会变成1,n-2,n-1,n-3,...中间很容易出现重复。我自己踩过的坑是在一个变式题里贪心写成每次都取当前中间值结果相邻差完全乱掉。后来总结出一个经验想让相邻差不重复本质上是让每次取的两个数之间的“间隔”单调变化。双端交替恰好保证间隔每次减1是最自然的方案。5.2 数组越界与奇偶错位排查方法如果代码里用了数组p而n是奇数循环到最后一个位置时l和r会相遇。比如n5时循环会依次取1,5,2,4,3最后一次取3时l和r同时指向3此时要注意l和r--不能让l超过r否则数组越界。更安全的做法是直接用公式法完全避免维护双指针的状态。奇偶错位也很常见。如果循环从0开始计数那么偶数下标对应的是左端小数奇数下标对应大数如果循环从1开始逻辑反过来。我建议在写每个分支时把第一个输出值代入检查一遍i1时应该输出1还是n心中要有数。代入法虽笨但查错非常快。5.3 STL容器的隐藏开销别让拷贝拖慢构造题刷题时经常有人用vector和deque来模拟双端取数尤其是deque前后插入删除很方便。但有一点需要注意deque在频繁push_front/pop_front时可能触发存储块重新分配和元素搬移如果元素是较大的自定义结构还会高频调用拷贝构造函数。虽然一般题目用不到这个量级但在构造题中如果n特别大用STL容器的效率会远低于直接公式计算。我看到过不少选手在赛场上用deque模拟两端取数结果跑出两倍的时间常数。对于2e5这种规模影响不大但如果n到1e6或更多建议直接用下标公式或双指针数组不要为了代码简洁牺牲性能。这也是为什么我最终选择公式法——它不需要任何容器也没有拷贝开销。5.4 输出超时问题构造题的最优解往往是O(n)输出这时候IO就是最大瓶颈。cin默认和stdio同步读入n之后输出n个数如果不关同步2e5的输出量在部分平台上可能变得很慢。我的习惯是统一加这两行ios::sync_with_stdio(false); cin.tie(0);如果你用printf输出则不需要额外处理但注意混用cout和printf时先关同步再混用会出问题建议全程只用一种输出方式。6. 构造题方法论的沉淀6.1 暴力枚举推导公式数学构造三板斧可以很暴力热词里有一条“暴力枚举推导公式数学构造”这几乎就是构造题的完整解法路径。第一步用DFS或手算枚举小数据得到一批可行解第二步从可行解里找规律形式化成序列公式或指针策略第三步用数学证明该规律对所有数据成立然后写代码。这个流程我屡试不爽。暴力枚举不是笨办法而是构造题最有效的探路工具。很多看起来高不可攀的构造题一旦你写出了n1到n10的可行解规律往往就浮现了。难点在于第二到第三步之间很多人能看出规律但不会证明导致心里没底。其实证明不一定要长篇大论像本题这样用“每对数的区间长度递减”就能讲清楚。6.2 怎么快速判断一道题是构造题做多了之后你会在读题阶段就嗅到构造题的味道。常见信号包括输出要求是任意解而不是最优解数据范围巨大但限制条件简单题目中出现“保证存在解”或“如果有多种解输出任意一种”等表述。这时候就要调整思路把目标从“求答案”变成“设计答案的结构”。还有一个信号是样例输出看起来很有规律。牛客的构造题样例通常会把某个规律性极强的解放在里面比如本题样例如果给出1,5,2,4,3你几乎可以反推出正解就是左右交替。所以拿到构造题先别着急认真观察样例很多时候样例就是构造规律的提示。6.3 从牛客练习赛到Codeforces构造题训练路线牛客练习赛的构造题质量很高适合作为入门和中期训练素材。我建议每次打完练习赛把所有构造题单独整理成一个标签页每道题记录三件事题目的核心限制、构造思路的一句话概括、关键证明。这比单纯收藏题解有用得多。如果还想进阶可以去Codeforces刷带有constructive algorithms标签的题从1100分开始逐步往上。CF的构造题风格和牛客略有不同更偏向短题面和大思维的跳跃。两个平台的题混着刷能让你对“构造”这个抽象概念形成更立体的理解。最后记得一点构造题没有固定模板但方法论是固定的——枚举找规律验证证明实现。最后再说一个实战习惯我在赛场上写构造题时会先在注释里写清楚每个变量代表的含义再写代码。左右交替这个思路虽然简单但一旦赛场上紧张很容易把左右两个指针的更新顺序写反。先在草稿纸上定义好再落到代码里能省下很多debug时间。这道“乘鲨破浪”带给我的最大收获不是那个漂亮的双端构造而是再次验证了构造题的通用解题路径先暴力枚举找规律再用数学证明锁死正确性最后用最简代码复现规律。