浅谈构造问题

构造题的解决方法较为丰富，感觉需要较多的人类智慧与灵感，但是一些套路的构造题通常会有以下几种构造方式。

递归/分治构造

我们能够解决一个较小规模问题的构造，而构造一个大规模的问题可以在构造完小规模的子问题后进行合并，从而完成构造。

CodeForces-1773K King’s Puzzle

题意：给你两个整数 $n,k$，你需要一张构造一张简单无向联通图，没有自环，使得点的度数集合大小恰好为 $k$。$1\le k\le n\le 500$。

如果我们能够构造出 $n=k+1$ 的情况，那么只需要在外面接一条链即可完成构造。

考虑该问题的特殊情况 $n=k+1$ 时应该如何构造。当 $n\le 3$ 时是容易的。

当 $n>3$ 时的 $(n,k)$，考虑构造子问题 $(n-2,k-2)$，然后再新建两个点 $(u,v)$，将 $u$ 与子问题中的 $n-2$ 个点一一连边，将 $u$ 与 $v$ 连边，这样能恰好使度数集合大小增加 $2$。

至此，本问题得到解决。

二进制构造

通常在构造限制为 $\log$ 时使用，按照每一个二进制位来拟合构造限制。

AtCoder-ABC108D All Your Paths are Different Lengths

题意：给定一个整数 $L$，你需要构造一张 $n$ 个点 $m$ 条边的带边权有向图，使得 $1$ 到 $n$ 恰好有 $L$ 条不同的路径，且路径长度分别为 $0\sim L-1$。$L\le 10^6$，你需要保证 $n\le 20,m\le 60$。

考虑先构造 $20$ 个点，相邻两点之间分别连两条边权为 $0$ 与 $2^i$ 的边，模拟二进制。

然后枚举 $L$ 的每一个二进制 $1$ 位，钦定前面的二进制都相同，这一位为 $0$，后面随意，只需要连到那 $20$ 个点中的某一个即可覆盖后面的所有 $0/1$ 情况。

该种构造方案的点数为 $\log L$，边数为 $3\log L$，符合限制，可以通过。

随机化构造

随机化构造方法适用在一些限制较为宽松，随机化成功率较高的问题上，也常用于部分乱搞算法。

CodeForces-1854E Game Bundles

题意：给定 $m$，你需要构造一个长度 $\le 60$ 的正整数序列，值域 $[1,60]$，使得恰好有 $m$ 个子集的元素和 $=60$。$m\le 10^{10}$。

考虑 $m$ 的数据范围非常大，尽管序列长度很小，还是很难找出确定性的做法。

考虑随机，先随出 $40$ 个 $[1,3]$ 中的元素，对其进行背包，算出用这些数组成每个 $\le 60$ 的数的方案数。

随后用一些 $>30$ 的数来填充剩下的序列，填充一个 $x$ 可以使总的子集个数加上 $f_{60-x}$。只需要贪心的添加即可。

分组构造

将一个构造问题分解为几个部分分别构造后组合而成，不同部分的构造将采用不同形式的构造方法。

CodeForces-1379E Inverse Genealogy

题意：给定 $n,k$，你需要构造一棵 $n$ 个点，且左右儿子大小差 $2$ 倍以上的点的个数（非平衡点）恰好为 $k$ 的二叉树，且每个点的儿子个数为 $0$ 或 $2$。$1\le n\le 10^5,0\le k\le n$。

考虑在确定 $n$ 时，$k$ 最少与最大分别应该如何构造。

对于最小的 $k$，不难发现直接构造一棵满二叉树即可，这样非平衡点的个数一定 $\le 1$。

对于最大的 $k$，考虑先构造一条链，为了满足 $0$ 或 $2$ 个儿子的限制，考虑在链上每个节点下再挂一个儿子。这样为了做到 $k$ 个非平衡点，最少需要点的个数为 $2k+3$。

因此考虑用两种构造方式合理地组合来拟合恰好 $k$ 个非平衡点的限制。

先使用第二种构造方式，构造出 $k-1$ 个非平衡点，随后在链的底端接上一个满二叉树，来补充剩下一个非平衡点即可。

对于非一般情况需要特判，但是不在本博客讨论的范围内，不做具体分析。

调整构造

首先根据题目要求构造出一个大致符合要求的构造方案，随后对方案进行调整来获得正确的答案。

CodeForces-1019C Sergey's problem

题意：给定一张 $n$ 个点 $m$ 条边的有向图，你需要构造一个点集，使得点集内的点两两之间没有边，且从点集内的点出发不超过 $2$ 步能够到达所有点。$1\le n,m\le 10^6$。

首先考虑忽略第一个限制，找出一个点集使得从这个点集出发走一步能走到所有点。

对于每个点维护一个标记，表示这个点是否能被当前点集中的至少一个点走一步后到达。依次枚举每个点，如果这个点未被标记，那么将这个点加入点集，并将这个点的所有出边能到达的点进行标记。

不难发现这样构造出的点集能在之多一条边内走到所有点，并且这个点集的导出子图是一个 DAG！

证明考虑记录每一个点被标记的时间戳 $t_u$，对于一条边 $u\to v$，如果 $u,v$ 都在点集中，那么一定有 $t_v< t_u$，否则在标记 $u$ 时一定会将 $v$ 标记。因此对于导出子图中的每一条边 $u\to v$，必有 $t_u> t_v$。因此这张导出子图一定是 DAG。

考虑对 DAG 拓扑排序，也类似第一次构造的形式进行标记，那么最终选择的点集内的点至少一步能走到第一次选出的点集，从而保证了至少两步能够到达所有点，也满足的点集内的点两两之间不变的限制。