构造

概述

构造题（Construction Problem）要求直接给出一组满足条件的方案，而非求最优解或判断可行性，答案往往带有随规模延续的规律。难点在于合法方案通常不唯一、自由度高，需要找出一种简洁、可描述、易实现的构造方式。常见思路包括观察小规模样例归纳规律、从限制条件反推结构，以及把问题转化为排列、数列、图等已知的构造模型。此类题目形式灵活、缺乏统一套路，须针对具体问题具体分析。

参考资料

• 构造 - OI Wiki

简介

构造题（Construction Problem）要求选手直接构造出一组满足条件的方案，而非求最优解或判断可行性。答案通常具有某种规律性，随问题规模增大仍可延续该规律。

构造题的核心挑战在于自由度高：合法方案可能有很多种，但需要找到一种「简洁、可描述、易实现」的构造方式。常见思路包括：观察小规模样例归纳规律、从限制条件反推结构、将问题转化为已知构造模型（如排列、数列、图）。

由于构造题形式灵活、无统一套路，解题时需要对具体问题具体分析。

例题

洛谷 CF743C Vladik and fractions

构造一组 $x,y,z$，使得对于给定的 $n$，满足：

$$\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=\frac{2}{n}$$

洛谷 CF1899F Alex's whims

树中两个顶点 $u$ 和 $v$ 之间的距离是指顶点 $u$ 到顶点 $v$ 必须经过的最小边数。

亚历克斯的生日快到了，蒂莫菲想送他一棵有 $n$ 个顶点的树。然而，亚历克斯是个喜怒无常的孩子。在 $q$ 天里，他每天都会选择一个整数，第 $i$ 天选择的整数用 $d_i$ 表示。如果在第 $i$ 天，树上没有两片距离 正好 为 $d_i$ 的叶子节点，亚历克斯就会很失望。

蒂莫菲决定送给亚历克斯一个设计器，这样他就可以随心所欲地改变他的树了。蒂莫菲知道亚历克斯也很懒惰，所以每天一开始，他可以进行 仅仅一次 以下类型的操作：

• 选择顶点 $u$、$v_1$ 和 $v_2$，需要满足 $u$ 和 $v_1$ 之间有一条边，$u$ 和 $v_2$ 之间没有边。然后删除 $u$ 和 $v_1$ 之间的边，并在 $u$ 和 $v_2$ 之间添加一条边。如果操作后图形不再是树，则 不能 执行此操作。

不知怎的，蒂莫菲设法找出了所有的 $d_i$。之后，他又想出了一个绝妙的主意——以防万一，为这组集合 $d_i$ 制作一本说明书，这样亚历克斯就不会失望了。