OI-wiki 构造题完全指南从题型特点到四大经典例题的构造思维【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki构造题Construction Problem是算法竞赛OI / ICPC中最常见也最考验创造力的题型之一。本文基于 OI-wiki 的 构造 一文系统梳理构造题的定义、两大核心特点并通过四道来自 Codeforces、洛谷、AtCoder 与 BZOJ 的经典例题深入剖析观察样例—归纳规律—推广构造的完整思考链路。读完本文你将理解为什么构造题高自由度反而让人无从下手并掌握若干可迁移的构造套路例如前缀和/前缀积构造完全 k 分图构造小物品 大物品的背包贡献分解等实战技巧。引入什么是构造题构造题是比赛中常见的一类题型从形式上来看问题的答案往往具有某种规律性使得在问题规模迅速增大的时候仍然有机会比较容易地得到答案这要求解题时要思考问题规模增长对答案的影响以及这种影响是否可以推广例如在设计动态规划方法的时候要考虑从一个状态到后继状态的转移会造成什么影响而在构造题中则要思考当输入规模 $n$ 变大时一个合法解能否按规律生长成更大规模下的合法解在 OI-wiki 中构造位于 算法基础 章节之下与枚举、模拟、递归分治、贪心等基础算法并列参见 mkdocs.yml 的导航配置同时它也是 竞赛学习路线 中动态规划入门一节的推荐前置技巧——文档明确指出在动态规划中最难的部分之一就是设计状态需要用到构造相关技巧可见构造能力是通往更复杂算法尤其是 DP 状态设计的底层思维基础特点高自由度与形式灵活构造题有两个非常显著的特点理解它们才能真正理解这类题目的难点所在1. 高自由度一道构造题的构造方式可能有很多种但是通常会存在一种较为简单的构造方式满足题意看起来是放宽了要求让题目变简单了但很多时候正是这种高自由度导致题目没有明确思路而无从下手——因为解空间太大反而不知道该从哪个方向入手2. 形式灵活、变化多样构造题并不存在一个通用解法或套路可以解决所有构造题甚至很难找出解题思路的共性这意味着学习者无法通过背诵模板来过关只能通过大量练习积累数感与构造直觉例题精讲四道经典构造题的思想内涵下面通过四道例题来体会构造题的思想内涵强烈建议大家先深入思考再查看题解这样的收益会远大于直接阅读例题 1Vladik and fractionsCodeforces Round #384 Div.2 C题目大意给定正整数 $n$构造三个正整数 $x,y,z$使得$$ \frac{1}{x}\frac{1}{y}\frac{1}{z}\frac{2}{n} $$解题思路从样例可以看出本题的构造方法观察目标等式一个自然的想法是利用单位分数分解的经典恒等式$$ \frac{1}{n}\frac{1}{n1}\frac{1}{n(n1)} $$把两边同时乘 $2$立即得到$$ \frac{2}{n}\frac{2}{n1}\frac{2}{n(n1)} $$但这里我们希望是三个分数之和于是可以做如下变形让两个分数各取 $\frac{1}{n}$把剩余的 $\frac{1}{n}$ 展开即令$$ xn,\quad yn1,\quad zn(n1) $$验证$$ \frac{1}{n}\frac{1}{n1}\frac{1}{n(n1)}\frac{(n1)n1}{n(n1)}\frac{2(n1)}{n(n1)}\frac{2}{n} $$特殊情形当 $n1$ 时无解这是因为此时 $n1$ 与 $n(n1)$ 相等都等于 $2$三个数退化为两个数无法构成合法解构造思路的来源本题的构造基本来自观察样例 一点点数感——看到 $\frac{2}{n}$ 与单位分数分解 $\frac{1}{n}\frac{1}{n1}\frac{1}{n(n1)}$ 的结构自然就能联想到答案此题对于数学直觉较强的选手来说并不难但它很好地展示了从常见恒等式出发的构造范式先猜出答案形式再代入验证例题 2Koishi Loves Construction洛谷 P3599题目大意给定 $n$解决两个子任务Task 1判断能否构造一个长度为 $n$ 的 $1\dots n$ 排列使其 $n$ 个前缀和在模 $n$ 意义下两两互不相同若能则给出构造Task 2判断能否构造一个长度为 $n$ 的 $1\dots n$ 排列使其 $n$ 个前缀积在模 $n$ 意义下两两互不相同若能则给出构造Task 1 解题思路先判断可行性当 $n$ 为奇数时无法构造出合法解当 $n$ 为偶数时可以构造形如$$ n,1,n-2,3,\cdots $$这样的数列即奇数位依次放 $n, n-2, n-4, \dots$偶数位依次放 $1, 3, 5, \dots$前后对称成对为什么 $n$ 必须放在第一位可以发现若 $n$ 不出现在数列首位则它出现位置前后的两个前缀和必然在模 $n$ 意义下相等因为 $n \equiv 0 \pmod n$ 不会改变前缀和的模值陷入模意义下相等的尴尬境地更系统的构造方式是这样的改从前缀和序列反推原数列设原数列为 $a_1,\dots,a_n$前缀和为 $S_i a_1\cdotsa_i$则 $a_i S_i - S_{i-1}$即原数列正是前缀和序列的差分序列若两个前缀和在模意义下相等它们的差对应原数列的某个区间和在模意义下就是 $0$会导致原数列中出现模 $n$ 意义下重复的值这与原数列是 $1\dots n$ 的排列矛盾因此前缀和序列两两之间的差在模意义下不能相等于是可以尝试让前缀和序列在模意义下呈$$ 0,1,-1,2,-2,\cdots $$这样的交替形式可以验证它完美地满足所有限制条件每个前缀和模 $n$ 两两不同且差分得到的原数列恰好遍历 $1\dots n$ 的每个值各一次Task 2 解题思路先判断可行性当 $n$ 为除 $4$ 以外的合数时无法构造出合法解当 $n$ 为质数或 $4$ 时可以构造形如$$ 1,\frac{2}{1},\frac{3}{2},\cdots,\frac{n-1}{n-2},n $$这样的数列这里分数表示模 $n$ 意义下的除法为什么合数无解对合数 $n$存在两个比 $n$ 小的数 $p,q$ 使得 $p \times q \equiv 0 \pmod n$例如 $3 \times 6 18 \equiv 0 \pmod 9$那么当 $p,q$ 都作为前缀积的因子出现过后数列的前缀积将一直为 $0$前缀积序列立刻失去两两互异性质故合数无解特殊地$4 2 \times 2$乘积中两个因子重合不存在满足条件的两个不同的 $p,q$因此 $n4$ 反而存在合法解——这正是一个特例破坏一般规律的经典陷阱如何构造与 Task 1 同样的思路——先确定边界$1$ 必定出现在数列的第一位否则 $1$ 出现前后的两个前缀积必然相等乘以 $1$ 不改变模值$n$ 必定出现在数列的最后一位因为 $n$ 出现位置之后的所有前缀积在模意义下都为 $0$分析题目给出的几组样例后发现所有样例中均存在一组合法解满足前缀积在模意义下为$$ 1,2,3,\cdots,n $$即第 $i$ 个前缀积恰为 $i$由此反推原数列第 $i$ 项应为 $\frac{i}{i-1}$取 $i1$ 时为 $1$最后一项为 $n$即上文给出的形式只需证明这些数互不相同即可这些数均为 $1 \cdots n-2$ 的逆元 $1$在模质数意义下逆元唯一因此各不相同此题得解这道题是从目标状态反推操作序列的绝佳示范不直接构造排列而是先构造满足条件的前缀和/前缀积序列再用差分/比值还原出原数列这一思路在后续学习中会反复出现例如 差分约束 中的同余状态构造、格雷码 的归纳构造等例题 3AtCoder Grand Contest 032 B题目大意给定整数 $N$构造一个节点数为 $N$ 的无向图节点编号为 $1\ldots N$要求满足这是一个简单连通图存在一个整数 $S$使得任意节点的相邻节点下标之和都等于 $S$题目保证输入数据有解解题思路通过分析 $n3,4,5$ 的小规模情况可以找到一个构造思路构造一个完全 $k$ 分图保证这 $k$ 部分的下标和相等完全 $k$ 分图中每个点与除自己所在部分之外的所有点相连于是每个点的邻点下标和都是全部点的下标总和减去自己所在部分的下标和即$$ S\frac{(k-1)\sum_{i1}^{n}i}{k} $$只要各部分的点权和相等所有点的 $S$ 就必然相等如何划分各部分若 $n$ 为偶数将下标前后两两配对${1,n},{2,n-1},\cdots$每对之和都是 $n1$各部分和相等若 $n$ 为奇数把 $n$ 单独拿出来作为一组剩余 $n-1$ 个下标两两配对${n},{1,n-1},{2,n-2},\cdots$单点组的下标和为 $n$每对的点权和也是 $n$依旧保持各部分相等这样构造出的图在 $n\ge 3$ 时连通性易证完全 $k$ 分图本身高度连通此处不加赘述且每部分内部无边、部分之间全连恰好是简单图此题得解本题展示了构造题中极其重要的一种手法对称分组、和值相等——通过精心设计分组让一个复杂的全局性质所有点邻域和相等退化为一个简单的局部性质各组下标和相等这种思想在构造图论题、构造数列题中都非常常见例题 4记忆中的背包BZOJ 4971Lydsy1708 月赛题目大意小 Q 曾解决过一道 01 背包问题给定 $n$ 个物品体积分别为 $v_1,v_2,\dots,v_n$从中选择一些物品也可以不选使总体积恰好为 $w$ 的方案数对 $P$ 取模的结果为 $k$现在他只知道样例输入中的 $w$、$P$ 和样例输出 $k$却记不清 $n$ 与 $v$请帮助小 Q 构造一组合法的样例输入即 $n$ 与各物品体积还原出这道曾经做过的题解题思路这道题可以说是自由度最高的构造题之一因为题目没有给出任何结构约束反而导致没有头绪、难以入手首先不难发现模数是假的由于我们可以自由构造数据一定可以让方案数不超过模数 $P$从而取模与否不影响结果问题退化为构造物品使方案数恰好为 $k$接下来是关键的构造设计构造 $n$ 个代价为 $1$ 的小物品加上几个代价大于 $\dfrac{w}{2}$ 的大物品这样做的好处是大物品体积超过 $\frac{w}{2}$意味着任意两个大物品不能同时被选否则总体积超过 $w$每个大物品至多取一件互不干扰小物品是原子单位用来精确调节方案数因此每个体积为 $x$ 的大物品对方案数的贡献是从 $n$ 个小物品中选出 $w-x$ 个来凑足剩余体积即$$ \dbinom{n}{w-x} $$于是整个问题转化为用若干个组合数 $\binom{n}{w-x}$ 相加拼出目标值 $k$定义状态 $f_{i,j}$ 表示有 $i$ 个体积为 $1$ 的小物品、方案数为 $j$ 时所需的最少大物品数用 DP 预处理出 $f$ 后即可反向查表构造出一组合法解通过计算可知只需预处理 $i\le 20$ 的所有值即可覆盖实际需求本题的构造思想可以概括为把大对象大物品视为一位二进制位式的独立贡献用小对象$1$ 体积小物品作为基数来微调这种大结构定规模、小结构调精度的分解手法在组合计数类构造题中非常实用从构造题到出题反向视角的启发构造题不仅是选手要面对的题型也是出题人设计数据时的利器OI-wiki 的 出题 文档在造数据的要求一节中专门提到为了防止针对特殊构造的特判被轻松过掉可以将不同的构造结合在一个测试点中或让数据的大部分是构造、掺杂小部分的随机数据中应当包含各种各样的构造即使你不知道什么错解会挂在这组构造上这从出题人视角印证了构造思维的价值——构造既是解题的钥匙也是检验算法正确性、卡掉错解的试金石总结构造题的思考方法论回顾四道例题可以提炼出几条可复用的构造方法论手法代表例题核心思想恒等式代入例题 1Vladik and fractions从常见数学恒等式出发猜出答案再代入验证目标状态反推例题 2Koishi Loves Construction先构造满足条件的前缀和/前缀积序列再用差分/比值还原原序列对称分组例题 3AGC 032 B通过两两配对使各组和值相等把全局性质化为局部性质大结构 小结构分解例题 4记忆中的背包大物品贡献独立、小物品精确微调用 DP 预处理查表特判规模边界例题 1、2留意 $n1$、合数等破坏一般规律的边界情形构造题没有万能模板但积累足够多的构造原型恒等式、分组技巧、反推手法后面对新题时更容易产生灵感建议读者在 OI-wiki 的 算法基础 章节中结合 枚举、贪心、分治 等内容交叉学习并配合 竞赛学习路线 中先掌握构造、再进入动态规划的顺序逐步建立起系统化的解题思维【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考