企业官网建设流程全解析

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. 形式灵活、变化多样

构造题并不存在一个通用解法或套路可以解决所有构造题，甚至很难找出解题思路的共性．这意味着学习者无法通过背诵模板来过关，只能通过大量练习积累"数感"与"构造直觉"．

例题精讲：四道经典构造题的思想内涵

下面通过四道例题来体会构造题的思想内涵．强烈建议大家先深入思考，再查看题解，这样的收益会远大于直接阅读．

例题 1：Vladik and fractions（Codeforces 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}{n+1}+\frac{1}{n(n+1)} $$

把两边同时乘 $2$，立即得到

$$ \frac{2}{n}=\frac{2}{n+1}+\frac{2}{n(n+1)} $$

但这里我们希望是三个分数之和，于是可以做如下变形：让两个分数各取 $\frac{1}{n}$，把剩余的 $\frac{1}{n}$ 展开，即令

$$ x=n,\quad y=n+1,\quad z=n(n+1) $$

验证：

$$ \frac{1}{n}+\frac{1}{n+1}+\frac{1}{n(n+1)}=\frac{(n+1)+n+1}{n(n+1)}=\frac{2(n+1)}{n(n+1)}=\frac{2}{n} $$

特殊情形：当 $n=1$ 时无解，这是因为此时 $n+1$ 与 $n(n+1)$ 相等（都等于 $2$），三个数退化为两个数，无法构成合法解．

构造思路的来源：本题的构造基本来自"观察样例 + 一点点数感"——看到 $\frac{2}{n}$ 与单位分数分解 $\frac{1}{n}=\frac{1}{n+1}+\frac{1}{n(n+1)}$ 的结构，自然就能联想到答案．此题对于数学直觉较强的选手来说并不难，但它很好地展示了"从常见恒等式出发"的构造范式：先猜出答案形式，再代入验证．

例题 2：Koishi 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+\cdots+a_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$，因此 $n=4$ 反而存在合法解——这正是一个"特例破坏一般规律"的经典陷阱．

如何构造：与 Task 1 同样的思路——先确定边界．$1$ 必定出现在数列的第一位，否则 $1$ 出现前后的两个前缀积必然相等（乘以 $1$ 不改变模值）；$n$ 必定出现在数列的最后一位，因为 $n$ 出现位置之后的所有前缀积在模意义下都为 $0$．

分析题目给出的几组样例后发现，所有样例中均存在一组合法解，满足前缀积在模意义下为

$$ 1,2,3,\cdots,n $$

即第 $i$ 个前缀积恰为 $i$．由此反推原数列第 $i$ 项应为 $\frac{i}{i-1}$（取 $i=1$ 时为 $1$，最后一项为 $n$），即上文给出的形式．只需证明这些数互不相同即可：这些数均为 $1 \cdots n-2$ 的逆元 $+1$（在模质数意义下逆元唯一），因此各不相同，此题得解．

这道题是"从目标状态反推操作序列"的绝佳示范：不直接构造排列，而是先构造满足条件的前缀和/前缀积序列，再用差分/比值还原出原数列．这一思路在后续学习中会反复出现（例如 差分约束 中的同余状态构造、格雷码 的归纳构造等）．

例题 3：AtCoder Grand Contest 032 B

题目大意：给定整数 $N$，构造一个节点数为 $N$ 的无向图，节点编号为 $1\ldots N$，要求满足：

• 这是一个简单连通图；
• 存在一个整数 $S$，使得任意节点的相邻节点下标之和都等于 $S$．

题目保证输入数据有解．

解题思路：

通过分析 $n=3,4,5$ 的小规模情况，可以找到一个构造思路：构造一个完全 $k$ 分图，保证这 $k$ 部分的下标和相等．完全 $k$ 分图中，每个点与除自己所在部分之外的所有点相连，于是每个点的邻点下标和都是"全部点的下标总和减去自己所在部分的下标和"，即

$$ S=\frac{(k-1)\sum_{i=1}^{n}i}{k} $$

只要各部分的点权和相等，所有点的 $S$ 就必然相等．

如何划分各部分：

• 若 $n$ 为偶数，将下标前后两两配对：${1,n},{2,n-1},\cdots$，每对之和都是 $n+1$，各部分和相等；
• 若 $n$ 为奇数，把 $n$ 单独拿出来作为一组，剩余 $n-1$ 个下标两两配对：${n},{1,n-1},{2,n-2},\cdots$，单点组的下标和为 $n$，每对的点权和也是 $n$，依旧保持各部分相等．

这样构造出的图在 $n\ge 3$ 时连通性易证（完全 $k$ 分图本身高度连通，此处不加赘述），且每部分内部无边、部分之间全连，恰好是简单图．此题得解．

本题展示了构造题中极其重要的一种手法："对称分组、和值相等"——通过精心设计分组，让一个复杂的全局性质（所有点邻域和相等）退化为一个简单的局部性质（各组下标和相等）．这种思想在构造图论题、构造数列题中都非常常见．

例题 4：记忆中的背包（BZOJ 4971，Lydsy1708 月赛）

题目大意：小 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 的 出题 文档在"造数据的要求"一节中专门提到：为了防止针对特殊构造的特判被轻松过掉，可以将不同的构造结合在一个测试点中，或让数据的大部分是构造、掺杂小部分的随机；数据中应当包含各种各样的构造，即使你不知道什么错解会挂在这组构造上．这从出题人视角印证了构造思维的价值——构造既是解题的钥匙，也是检验算法正确性、卡掉错解的试金石．

总结：构造题的思考方法论

回顾四道例题，可以提炼出几条可复用的构造方法论：

构造题没有万能模板，但积累足够多的"构造原型"（恒等式、分组技巧、反推手法）后，面对新题时更容易产生灵感．建议读者在 OI-wiki 的 算法基础 章节中结合 枚举、贪心、分治 等内容交叉学习，并配合 竞赛学习路线 中"先掌握构造、再进入动态规划"的顺序，逐步建立起系统化的解题思维．

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki