构造题怎么想才不容易乱：骨架、接口、余量与收口

做构造题时，人很容易一上来就想完整答案。位置、数量、相邻关系、边界和奇偶性全挤在一起，思路很快就分叉了。

其实比赛并不要求我们描述所有合法答案。对每个可行输入，找到一个能稳定生成、也容易证明的答案就够了。为此，我们可以主动缩小搜索范围，只研究一族比较规整的解。

这就是“可控解族”：

它不必包含所有合法答案，但要覆盖所有可行输入。

对按前缀扩张、分块拼接或递归合并的构造题，可以先沿着这条线思考：

\text{骨架}\rightarrow\text{接口}\rightarrow\text{余量}\rightarrow\text{收口}\rightarrow\text{证明}

这套框架并不包打天下。显式代数构造、概率构造、随机重采样，以及需要反复换边或增广的题，未必适合硬套。不过在常见的模块化构造里，它很管用。

把答案看成一个仍然做得完的半成品

构造过程中，可以把当前状态压成四部分：

(P,B,R,U)

其中：

$P$ 是已经固定的部分；
$B$ 是旧结构对未来影响的接口；
$R$ 是尚未满足的要求；
$U$ 是还没用掉的位置、元素、模块或操作。

每次加入一个新模块 $M$ ，状态发生一次转移：

(P,B,R,U)+M\longrightarrow(P',B',R',U')

一般来说，应把它写成：

(B',R',U')=F(B,R,U,M)

只有当模块贡献彼此独立、能够直接相加时，才能简化为：

R'=R-\Delta(M)

这点容易被忽略。比如新增逆序对的数量，往往取决于新模块放在什么位置；连通块数量也不能只靠普通减法更新。先确认贡献是否真的可加，再写贡献公式。

整个过程中至少要守住两个不变量。

当前没有留下不可修复的错误

中间状态不必已经满足全部题设。例如最终要求图连通，构造到一半时当然可能还没连起来。

这里的“合法”指的是：

没有重复使用元素；
没有产生禁止出现的环或交叉；
没有让某个点的度数超过上限；
暂时未完成的要求仍被记录在 $R$ 中。

当前状态仍能扩展成完整答案

这是更容易漏掉的一条。

有些选择眼下完全合法，却已经耗尽了关键资源。继续做几步以后才发现，剩余数量补不出来，最后两个端点也接不上。

所以，不能只问“这一步有没有错”，还得问“走完这一步以后，后面是否仍然有解”。

最好维护一个容易检查、而且已经证明足够强的条件。容量、奇偶性和模数通常只能帮我们排除明显无解的状态，不能自动保证后缀一定能完成。

先决定每类条件由谁负责

读完题后，不妨先给条件分工。这个分类不是唯一的，但能避免所有约束同时挤进脑子里。

难以补救的条件交给骨架

元素不能重复、路径不能相交、图不能成环，这类错误通常不好返工。可以让构造框架从一开始就排除它们。

例如，构造连通无环图时先搭一棵树；构造排列时先确定元素的唯一归属；处理棋盘时按行或按层推进，让已经封闭的区域不再改动。

骨架不用包办所有要求。它只处理最危险的部分，剩下的位置还要留出几个可调的“旋钮”。

新旧部分之间的关系交给接口

接口 $B$ 必须是过去信息的充分摘要。

换句话说，给定 $B$ 以后，被丢掉的历史不能再影响后续模块是否合法。若新的一行只会和上一行冲突，那么接口可以只保存上一行；但“只记上一行”本身不是证明，还要说明更早的行确实不会直接影响当前行。

接口可能是一段边界，也可能只是几项状态：

最后一个数或路径的两个端点；
上一行的放置情况；
当前奇偶性；
各连通块的代表元；
尚未补齐的度数；
几个仍然开放的连接口。

顺序选得好，新模块只需检查这一小块信息，不用每次重新扫描全部旧结构。

数量要求放进剩余状态

还差多少总和、长度、边数、逆序对或点度，都可以记入 $R$ 。剩余资源则单独放进 $U$ 。

这个区分很重要。“还差 5”和“还剩哪些东西能拿来补 5”是两回事。

如果目标有多个，可以记录贡献向量：

\Delta(M)= (\Delta\text{数量},\Delta\text{总和},\Delta\text{奇偶性},\ldots)

目标之间可能耦合。这时未必能贪心扣减，接口状态较小时，用 DP 维护精确可达集合往往更稳。

边界和余数留给收尾

首尾连接、最后几个度数、块大小留下的余数，通常没必要每一步都处理。

更实际的办法是提前空出几行、几个点或一个整块，专门解决最后的接口状态。先别急着填满。

让答案按一个小接口慢慢长出来

骨架确定以后，还要选生长方向。

序列通常从左往右做，矩阵按行或按层扫，树可以从叶子往根合并。图论构造有时先画主路径，再往两侧挂结构；递归构造则分别完成两个子问题，最后通过固定接口合并。

判断方向是否合适，主要看一件事：每加入一个模块，需要回头检查多少旧信息？

如果加一行就得重新检查前面所有行，接口多半太大。若只看上一行或几个端点，后面的证明也会轻很多。

每准备放一个模块，可以用下面四问检查。

它贡献了什么？
新增多少元素、边、总和或度数？改变了什么奇偶性和接口状态？
接缝会不会出问题？
模块内部可能早已验证过，真正容易出错的是新旧交界处。还要确认它不会绕过接口，与更早的结构发生额外冲突。
放完还剩多少自由度？
是否还有模块可以翻转、交换或延迟决定？最后几个位置是不是已经被提前占满了？
剩下的目标还做得完吗？
容量够不够？奇偶和模数是否匹配？当前接口是否还存在收尾模板？如果没有直接证明，就维护一个 DP 或预先枚举出的可达状态集合。

这四问不用变成僵硬的流程。它们更像卡住时的检查表。

人为限制可以很强，但必须保住输入覆盖

设输入 $x$ 的所有合法解为：

\mathcal S(x)

为了方便构造，我们规定“每行使用固定模板”“路径不能向左”或“答案必须对称”，于是只考虑：

\mathcal T(x)\subseteq\mathcal S(x)

缩小解空间没有问题，甚至通常是好事。需要证明的是，对每个可行输入 $x$ ：

\mathcal T(x)\neq\varnothing

也就是限制加完以后，仍然至少能构造出一个解。

每增加一条人为规定，记下它的作用和代价就够了。

例如规定“每行恰好放一个上箭头”，好处是行结构固定，行间接口容易分析；代价是每行对箭头总数的贡献也被固定了。如果目标数量变化很大，普通行可能覆盖不了全部输入。此时可以允许少数特殊行，或者把最后几行留作调整区。

再比如规定“主路径不能向左”。它能减少回绕，使两侧区域更容易描述，但可能排除某些必须绕行的形状。正确的处理不是立刻放弃路径，而是检查所需的区域规模能否仍由单调路径实现；如果不能，再加入一种有限的回绕模块。

可达性通常分两层检查。

先做便宜的排除：

剩余容量是否小于欠账；
最小贡献是否已经超过目标；
奇偶性和模数是否匹配；
模块贡献的最大公约数是否允许目标值。

这些大多只是必要条件。

接着还得证明：在当前接口和资源下，剩余模块确实可以覆盖目标。状态少时直接 DP；贡献形成连续区间时证明区间可达；模块种类有限时，也可以预先枚举所有能收口的状态。

假设初始贡献为 $0$ ，普通模块每次贡献 $2$ ，那么普通模块只能覆盖偶数目标。如果再加入一个贡献为 $1$ 的修正块，奇数目标也有机会覆盖。

这里仍有三个前提：贡献能够独立相加，修正块在所需接口上放得进去，剩余空间也够。少一个都不行。

路径分区也类似。若冲突是局部的，分隔路径可以让左右两侧分别检查合法性；但总数量、连通性等全局条件仍会耦合两侧，配额还得一起算。

普通模块铺主体，收尾模块处理麻烦状态

周期构造里经常出现：

n=qk+r

前面铺若干个大小为 $k$ 的标准块，最后按照余数 $r$ 选择模板。有时余数本身不好收，还要少铺一个标准块，把 $k+r$ 的区域一起交给收尾。

这比贪到最后再补救稳得多。

如果接口状态有限，而且每种可达状态都有大小统一有界的收尾模板，那么只需预留 $O(1)$ 的区域。不是所有题都有这个性质。有些题要借用前一个整块，或者保留 $O(\log n)$ 规模的调整区，甚至需要一次较大的全局修正。

因此，收尾区的大小也要证明，不能因为常见就默认它是常数。

常见的收尾任务包括奇偶修正、首尾相接、最后几个点的度数，以及标准块无法处理的余数。小规模输入通常也在这里单独列出。

卡住时，先查三类结构性问题

一个构造走不下去，不必马上推翻重来。可以先检查下面三类问题。

接不住

新模块会和很多旧元素冲突，每加一步都要回头扫描整个答案，两个子结构也很难合并。

这通常说明接口太大，或者接口漏掉了必要信息。可以换生长方向、增加边界状态，或者重新划分模块。

调不到

结构一直合法，但总数只能按固定步长变化；奇数目标永远差一，某些规模也始终表示不了。

问题多半出在模块贡献集合太单一。可以增加修正块，延迟某个决定，保留可翻转的位置，或者用 DP、匹配、流来选择具体模块。有些题里，这些算法也会反过来决定骨架。

收不了

中间模式跑得很好，最后几个位置却怎么都封不上，首尾连不起来，或者只剩一个尴尬余数。

这一般意味着收尾区留晚了或留小了。提前停止普通扩张，多留一个块，或者从两端同时构造，往往比硬补最后两格更有效。

这三类诊断并不穷尽所有错误。可行输入判断错了、不变量没证对、构造不终止、复杂度超限、元素重复或数值溢出，也要检查。只是遇到结构性卡顿时，先看“接、调、收”，定位通常会快一些。

证明要沿着构造顺序写

构造的证明最好和算法同方向，不要构造时逐步生成，证明时又突然从全局重新观察。

一份比较稳的证明通常包括：

初始化
初始骨架满足不变量，初始接口和剩余状态定义正确。
模块内部合法
每类标准模块、修正模块和收尾模板内部都满足局部要求。
接口充分
证明接口保留了过去对未来的全部影响。完成这一步以后，添加模块时才只需检查模块内部和当前接口。
状态转移正确
新接口、剩余需求和剩余资源更新无误；若使用贡献公式，还要证明贡献可加。
可完成性保持
每一步之后，当前状态仍在已证明可完成的状态集合中。
终止
选择一个有下界的整数势函数，并证明每一步都严格减小。这样才能推出构造会在有限步内结束。
收尾覆盖
所有可能到达的尾部状态，都有对应模板或可达性证明。
全局目标与复杂度
汇总模块贡献，证明最终数量、度数或总和准确，同时说明时间、空间和输出规模。

比赛时，可以先在草稿纸上写下面这些：

题目硬性要求：

哪些错误一旦出现就很难修：

我采用的骨架：

生长单位和生长方向：

接口保存什么：
为什么这些信息足够：

剩余需求 R：
剩余资源 U：

加入一个模块后的状态转移：

为了方便，我额外规定了什么：
- 它解决了什么问题：
- 它排除了哪些答案：
- 为什么仍覆盖所有可行输入：

必要性筛选：
- 容量：
- 奇偶：
- 模数 / gcd：

真正保证可完成的条件：

收尾区域和收尾状态：

如果卡住：
- 接不住？
- 调不到？
- 收不了？

这套框架不替代具体技巧。按行扩张、路径分区、递归、对称和分块，主要解决结构怎么搭；贪心、DP、匹配或流，则常用来决定模块怎么选。把这两层分开，构造题通常就没那么容易乱了。