声明
本文非严谨的算法理论研究，仅仅是个人对解题经验的归纳和实验性的系统总结，不保证理论上的完备性与纯粹性。仅对解题实践提供一个较为自洽的解释，作为参考。
本文所有题都不会提供题意和完整包含细节的题解，也就是说您需要先做一遍或看其他题解，因为没有做题经验就无法感受解题思想。您也可以把本文理解成一个归类好的题单。
如果一题包含多项技巧则会放在多处，但如果包含多项思想则只会在一处解说。如果出现一题多解会记入多个类别并多次解说。
带括号的题是内部训练题。
如果您认为一些理论表述有偏颇，或找到文章无法解释的题目（反例），可以告诉我。
本文会时常更新。
引言
在 OI 中，“构造题”的定义是什么？我也没法给出一个精准的答案。似乎这类题确实有某些明确的特征，但这一概念的边界却是模糊的。广义地来说，所有算法都是构造——dp 构造状态和转移，ds 构造维护的结构……但我们常说的构造更多的是一种无算法的构造，或者说，不是将问题模型转化成一种特定的算法所能解决的问题，再去间接求解，而是直接去构造所求组合结构。
最关键的是这类题的思维方式很特殊，这使曾经的我面对构造题不知如何下手。其余类型的题都主要侧重于分析，通过分析问题模型的性质，刻画其结构，从而将它转化成更容易解决的模型。而构造题则往往给人一种“凭空”出现了答案的感觉，例如，考虑一个方式/过程/结构，它刚好就是对的，然后就解完了。另外，其他类型的求解型问题往往是以最优化为目标，某些不要求最优化的题可能还得硬转成最优化（例如一些流问题），而构造题则倾向于消去最优化目标。当然也不能否定，构造和其他算法是密切相关的。
不存在简单地区分构造和非构造题的方法。解题后期如果感觉解的可能性很复杂，无法用简单的方式统一描述，那就需要考虑 dp、网络流等方法，否则可以尝试直接构造。这其实是废话。
接下来，我会介绍解构造题的技巧和方法。所有归约 dp、差分约束、2-SAT、流、线性规划的题，以及交互、部分数学求解方面的构造这些非构造组合结构而是构造求解方法的题均不会讨论，我也会尽量避免无法证明概率的随机化构造题。
分类
这部分其实对解题没啥帮助……
构造题的所求一般来说有以下几类：
凭空构造一个结构或补充结构；
安排（排列、划分、组合、选一部分）给出元素；
构造一系列操作以达到目标。
另外可以关注以下几个特征：
输入是否是 O(1) 的；
是否有可能无解；
是否要求最优化。
基于特性的技巧
以下题例可能不完全是构造题，但如果某个技巧没法出到构造题里就不会收录。
括号序列相关技巧题例
前缀和化。将左右括号分别视作 ±1 并作前缀和，画出折线图。能给 flip 和 reverse 提供一个直观的几何解释，还能处理 min/max 相关，以及利用类介值定理证明存在性。
CF1458D、CF1685C
路径化。将左右括号分别视作向右和向下，画出折线图。与上一种类似。
匹配括号连弧线。
CF1503F
括号树。根据定义，合法括号序列一般有两种观察方式：多个括号序列拼接并在外面套一对括号：(ABC...)，以及找到开头括号匹配的右括号将序列分成两块：(A)B。这两种分别对应着正常括号树与三度化后的括号树。
序列变换
排列相关技巧题例
画点。在平面直角坐标系中画出 (i,pi) 是一种直观反映偏序关系的方法。
排列
按值域构造。一种是以某种顺序扫描值域，另一种是只维护相对大小关系，每次插入再在值域中空出一个位置给新元素。这样可以减少构造受限性，可以用增量思想构造。
置换环。涉及置换、交换使排序这类的题都可以把 i→pi 画出来。还有类似的排列转有向图的处理方法。
CF1491G、CF1656G、CF1787F、
THUPC2024 初赛
排序大师
考虑逆置换。
CFgym102154C
拓扑序。用 DAG 的拓扑序来理解所求的排列。
CF1477D、CF798E
逆序对数。常用于分析无解。
CF804E、（樱花抄）、
互测 2022
魔术师
贪心。要求排列字典序最小时，逐位贪心判断可行性即可。
CF1530E、CF1844F1、（roast）
二维相关技巧题例
拆成一维。
CF417E、（巧克力）
转 45∘。
喷泉公园、 视觉程序
拼图法。找到构造中的小单元去试探。
CF1628C、CF1034B
棋盘染色。即按 (x+y)modk 将格子分类，保证长为 k 的段必然包含每类各一个，用于加强命题方便构造，或判断无解。
CF1450C2、CF763B、CF1268B、CF1485D
拓扑学方法。主要包括转向度数和、穿过次数奇偶性、欧拉定理、皮克定理。
行列和。作为守恒量用于判断无解。
CF1672G
数论相关技巧题例
互质对构造。(n,n+1)、(n,2k−1)（n 奇）、(p,n)（p 质）。
CFgym102055C、LOJ3392、CF922F、
互测 2022
大冬天题
拆二进制以及辗转相除法。
CF341E
原根。乘转加。
互质/整除图。可以更加直观。
CF1148G
预处理常数。如果只允许使用特定材料构造出某个数，那么可以考虑先用方程把相关要用的常数解出来，然后用二进制拆分等构造。
CF1060H、CF1427E
模意义下考虑。如果条件是不等式，那么模意义就是加强条件；如果是等式，那就需要倍增。
CF1218G、CF1844G
生成树相关技巧题例
归约最小/大生成树。
CF1054G
叶子调整法。叶子是树中最灵活的部分，就像质数在数论构造中的作用。可用于保证某个相关数值“能够调整至任意一个 内的值”。
CF1311E、CF1098C
边权为标号差绝对值的最大生成树。前一半连 n，后一半连 1。
CF1474E、CF1656F
图论相关技巧题例
考虑反图。
利用 ∑deg=2m 来均摊。在处理实现细节，确定枚举方式时可以提供依据。
CF1444C
找 dfs 树。往往可以简化构造。
CF1680F、 景点划分、CF1515F
缩点。
考虑二分图。
CF1515F、CF1218G、
湖北省选模拟 2023
棋圣
进行 bfs。主要是从邻边和距离视角观察。
CF1470D、CF1368E、CF1019C、CF794D
竞赛图性质。存在哈密顿路、可分层、度数最小的点到其他点距离均 ≤2。
CF1779E
图相关序列判定定理。包括 Erdős–Gallai 定理、Landau 定理等。
USACO14MARGoldT3
邻接矩阵。
AGC061B
赋点权来决定边权。
CF42D
互斥条件。有一类题目是要求在图中找两种结构之一。先尝试找一种，假设找不到再试另一种。
CF1364D、CF1148G、CF1439B、（ schrodingersjerry 和图染色）
格雷码
格雷码的本质是利用二进制表示的唯一性，来保证每种数恰好出现一次。
题例：CF1673F、ARC138D=P7949、CF1163E
欧拉回路/路径
遇到类似与“相关和为 0” 的守恒条件时可以考虑用欧拉回路/路径构造。
题例：CF1634E、CF1610F、CF1458D
鸽巢原理
鸽巢原理一般用于有多个备选项，它们从总体来看有某个数量关系，可以导出存在一个个体满足特定条件。偶尔也反过来用证明无解。在实际应用中，备选项可能是给定模型的局部，也可能需要自己构造，后者会比较难，关键在于找到可能性足够少的“鸽巢”。
例：CF1450C2、CFgym102900B、CF1515F、CF1090C、CF618F、CF1835C、 量子通信、 制作菜品
绝对众数
涉及到绝对众数最简单的模型就是：排列一些数使得相邻数不同。这类问题要抓住主要矛盾，其他次要矛盾都会自动消解，就可以专注于构造一个内容。另外这类题常使用逐步构造。
另外，对于树上问题，通过找重心作为根可以避免出现大小为绝对众数的子树，这也是一个简化讨论的技巧。
例：CF1242E、CF1762G、CF1329D、 景点划分、ARC156C
题外话：用爬山或退火构造时也常常会先满足最紧的限制，体现形式也往往是类似绝对众数的东西。详见此处。
Dilworth 定理
往往给人一种“双向限制”的感觉。
例：CF1097E、CF1738G、CF1630F
简单写一下相关的证明：
最长链 = 最小反链覆盖：≤ 显然，≥ 每次剥掉一层入/出度为 0 的点。
最长反链 = 最小链覆盖：≤ 显然，≥ 删掉一个出度为 0 的点 u 归纳，取出覆盖方案的每条链中最后的能出现在最长反链里的点，如果没有一个与 u 有偏序关系则最长反链 +1，否则最长反链不变，且有一个点 ≤u，取出它所在的链中所有能出现在最长反链里的点与 u 共同作为一条链，剩余的点最小链覆盖也 −1，总体不变。
求最长反链法 1：取二分图最大独立集中两部均在内的点。记最小链覆盖为 s，则最大匹配为 n−s，最大独立集为 n+s，两部均在内的点至少 s 个。
求最长反链法 2：求出所有可能在最长反链中的点，每次任选一个，删除与它有偏序关系的点，归纳。
常用的解题思想
所有解题思想之间大多没有明确的分界，往往结合使用。
a. 等价表述条件和观察模型
使用不同的方式和图形去表示问题模型，可能会突出问题的某一部分特征，从而带来新的启发。有一个经典的例子可以说明换一种方式描述会产生多大的区别（一道 dp）：CF1368H1。原问题（最大流模型）和最小割模型都看似无法解决，但如果转变到平面图最短路的角度去分析出路径的简化性质（每行或每列均相同），再回到最小割模型，就可以 dp 了。因此，不要认为等价模型没有意义，否则会错失动机。
在转述过程中要注意可能会不小心加强模型或丢性质，反而导致无解，这个后面会提到。
例：
CF1680F：奇环上会出现两端均选的边。因此原题意可以转述为“删除一条边使得图变成二分图”，dfs 树讨论即可。CF1110E：经典套路，这种就两类，(ai−1,ai,ai+1)→(ai−1,ai−1+ai+1−ai,ai+1) 作差分解决，(ai−1,ai,ai+1)→(ai−1+ai,−ai,ai+1+ai) 作前缀和解决。CF1458D：将 01 序列转化为前缀和序列化成折线，从而将奇怪操作翻译成区间翻转。容易用调整法证明任意符合守恒条件的序列均可达到。因此可用欧拉路径的方式去描述合法折线，从而贪心。CF1054G：“集合内所有点形成一个连通块”等价于“集合内所有点之间边共有 size−1 条”，加之边不可能多于 size−1 条，故原条件可以转述成“所有集合的点之间边数量之和取到理论上界”，这就可以用 MST 了。边权用 bitset 加速计算。b. 将无解和最优化条件转成已知条件
首先是经验：CF 中如果 Output 里说无解输出 −1 但 Example 里没有 −1，那么就不会有无解的情况。
部分构造题有一个很大的特点，就是在解题开头就确定无解条件或最优解公式，也就是先确定充要条件的一边，去构造另一边，或是先给出不等式的一边，再构造取等。可以说这是一种“先猜后证”，也为构造增加了提示。当然这种猜测要足够谨慎，尽量思考通过题目条件能推导出的必然性，以及从数学角度去分析模型（找到模型的某个示性数，或守恒量）。
不是所有构造题都可以使用这个技巧，同时要避免将非构造题误判成构造（例如，有时无解和最优化情况必须通过 dp 求出）。关键是通过分析条件来感知题目模型的解是可以用一种特定的规律描述，还是要根据输入数据，去遍历所有可能的解才能确定。
例：
CF1543E：对于第二问，首先分析图的点与边的数量关系。每个点恰有一个颜色 x 的邻居，一个颜色为 x 的点会作为 n 个点的邻居，因此一共有 2n/n 个颜色为 x 的点，所以原问题在 n=2k 时无解。这个无解条件反过来启发我们使用递归构造和拆分二进制的思路去构造 n=2k 的情况。可参考 3b1b 的视频。 单调上升序列：套用题面中给出的证明，可得到最优解 ≥n−1。并且达到 n−1 时限制是很紧的，遂考虑每一轮安排边权使得所有“探险家”均走一步，也就是将完全图的边划分为 n−1 组完美匹配。c. 从特殊情况获取提示
特殊情况包括特殊输入和特殊解，这一条侧重于特殊输入。这样思考的帮助是：
通过特殊情况的解获取一般构造的线索；通过将所有情况用某些手段归约到特殊情况，从而只需解决特殊情况；通过构造极端输入确认无解性/答案上下界，或排除不可能的构造方法。
但是不是所有题的特殊情况都能给出有效的提示，有时候反而会起到误导作用。要很警惕的一点是一些不成熟的思路可能会被构造的极端情况排除掉，但是实际上改一改就对了。
例：
CF1311E：先考虑完全二叉树和链的特殊情况，然后寻找能符合题意的，处于两种特殊情况之间的“连续的”变化，调整法。CF1515F：结合 b，有足够的理由猜测 ∑ai≥(n−1)x 即有界，于是任意图就可以归约到树这一特殊情况。然后根据 b 的数学上分析（核心分析：如果有一条边不能并那么一定存在一个点 au>x），结合鸽巢原理，构造出一个合并方法。CF618F：考虑 B={n个n} 的情况，容易想到将 A 作前缀和后对模 n 余数鸽巢，这样就把正解的提示都集齐了：鸽巢、前缀和、A 的前缀和减 B 的前缀和。CF1019C：一种思路是，考虑 DAG，可以做到任何不选的点都能被选的点走 1 步到达；稍稍加强，考虑对原图 dfs 后只有树边、前向边和返祖边，树边和前向边就相当于 DAG，返祖边导致的矛盾可以通过取消选择祖先那个点，同时保证至多走 2 步可达。推广到一般情况，将原图拆成两张 DAG（根据边的起终点的编号大小关系分），套用原来的方法即可。
作为一个反例：我在解这道题时考虑了竞赛图这一特例，这没有帮助，反而把方向带歪到关注节点度数上去了。因此要多考虑几种特殊情况，并结合分析筛选。AGC064B：如果不考虑特殊情况，容易考虑使用 j，每次找一个点，周围只有一条可行（加入不成环）同色边，选择这条边。这样思路就走歪了。正确的思路是先考虑一些无解情况，发现点边颜色均交替的偶环无解，进一步分析发现如果要形成一棵树，就必须有一条边，两端的颜色都与它相同（记为一类边）。进一步地，发现如果存在一个点，它不断走这样的边 uev（u 和 e 同色，与 v 异色，记作二类边），最后走不到任何一类边，那就无解了。因此先尽量选所有一类边，然后再从这些边的端点向外扩展二类边（一个点只能被扩展到一次）。如果所有点都被扩展到了，再用剩下的边尽量连接这些森林即可保证有解。d. 分析数量关系
模型的数量关系可能不仅仅能用于 b，而且能指导构造的过程。往往结合待定系数法，列出方程或不等式来分析。c 例 2 就是一个典型的例子。
例：
CF1667C：设答案为 k，则有 (n−k)×(n−k) 的部分只能用对角线覆盖，故 2(n−k)−1≤k⇒k≥(2n+1)/3。固定右下这样一个空矩形，剩余部分试探构造即可。换句话说，下界分析直接给出了构造思路。
CF1158B：经过一些尝试，直觉上串必须要有循环节，长设为 l。长 0，发现存在一个策略只需两步，因此问题变为判断答案是否为 0 或 1，可以暴力。CF1685C：打表发现 ans≤2，结合括号序列技巧画图可得，以前缀和最大值为界左右各翻转一次，一定可以完成，因此只需讨论答案是否为 1。CF1781G：尝试构造达到理论下界的解，可以使用归约构造，逐步删掉儿子均为叶子的点的子树，base case 分讨即可。同样 ans≤2。CF1852E：刻画完结构后发现未知元素的可能性太多了，但是可以找到性质，只有至多一种未出现过的数被填入，并且它一定是某个出现过的数 −1，且可以较简单地确定它填的情况，暴力枚举这种数即可。CF1375F：不必多说。f. 加强构造条件
这个方法很像数竞不等式放缩的过程。有时构造的限制太松了，反而不知道如何下手。通过加强构造条件减少可能性是构造题非常常用的手段，它可以体现为通解、逆向、归约、调整、分治等复杂的技巧，在后面会提到。这一节以较为初级的增强限制和减少变量为主。
在构造的过程中自然地加强和通过模型特征提示试探加强是加强构造条件的两个主要方法，加强过程中要保证有解性或最优性不变（否则就像不等式放缩过头）。考虑特殊情况下“必须得怎么构造”也能给加强条件指明方向（例 5&6）。
在条件分析不下去的时候，也可以跳出复杂的关系限制，冒无解的风险去尝试一些特定的构造策略，有可能它刚好就符合了所有要求，或者有少量不符合可以微调改对。例如 yhx 在 WC2022 上讲的 喷泉公园 的贪心构造做法，就是通过试探得到的。
总的来说就是不要因为题目给的条件无从下手就懵了，要主动尝试一些可能性。
例：
CF1599A=ISIJ2021CupT3：题目条件给人一种“可以任意改变左右和大小关系”的感觉，考虑一种大小关系的必然性（加强）：左右砝码可以配对，所有对要么都是左边大，要么都是右边大。容易想到排序 a1⋯n 后连续段交替取，可以保证有解，就解完了。CF1270G：考虑将 ai 换元使得所有变量的限制条件都相同，否则感觉不好处理。令 bi=i−ai，则 bi∈，目标条件转化成 ∑i∈Sbi=∑i∈Si。考虑加强，试图使得每个 bi 都等于一个 i′，类似回路的结构可以满足该条件。建 n 点图连边 i→bi，找个基环即可。CF1835C：作前缀和，目标转化为找到 0≤am/2 的数调整不会导致贡献的连锁改变，可控性较强。m 足够大时 σ0(m)≤(m/2,m) 中的质数数量，m 较小时可以直接贪心，打表验证。
网络站点：先考虑直接用 dfs 序，发现最后一个儿子的子树与本身子树外后 dfs 到的节点无法区分，因此考虑调整为所有儿子记出栈时间，以此类推，按层数奇偶性决定记入栈还是出栈时间戳。
喵了个喵：思考 subtask 1，每个栈维护两个牌，分别记为“底”和“顶”。留一个空栈用于消底。在 k=2n−1 时仅有所有种类牌均存在 1 张时会出问题。出现这种情况时不应贸然将最后一种牌（记为 x）放到仅有的空栈里——如果下一步消的是一个底，那么 x 直接放到这个底对应的顶上。推而广之，这启发我考虑后面第一个消底的步骤，在这之前消的都是顶，好处理。如果这个底对应的顶在期间出现了偶数次，那么也可以将 x 放在这个顶上，否则 x 可以放在空栈里。这样的话当消第一个底后至少留有一个空栈。如果后面第一个消底之前先消了 x，则可以直接把 x 放在空栈里。
这题实际上最恶心的是实现。
m. 做法拼合
用这类方法的题较少见，其主要难点在于找到一个分界条件，使得两种做法恰好能完美覆盖所有情况。一个重要的点是不要因为一个构造方法不能解决整个问题就把它舍弃掉。
常用于找图的一部分，满足两个条件中的一个这类问题。
例：
CF1097E：发现上界至少是 f(n)=max{k∣k(k+1)/2≤n}，可由 取到。一个基本的归约思路是每次取 LIS 和 LDS 中较长的删去，但通过随机大数据筛选发现这个长度可能
