跳转至

# 构造

本页面将简要介绍构造题这类题型．

## 引入

构造题是比赛中常见的一类题型．

从形式上来看，问题的答案往往具有某种规律性，使得在问题规模迅速增大的时候，仍然有机会比较容易地得到答案．

这要求解题时要思考问题规模增长对答案的影响，这种影响是否可以推广．例如，在设计动态规划方法的时候，要考虑从一个状态到后继状态的转移会造成什么影响．

## 特点

构造题一个很显著的特点就是高自由度，也就是说一道题的构造方式可能有很多种，但是会有一种较为简单的构造方式满足题意．看起来是放宽了要求，让题目变的简单了，但很多时候，正是这种高自由度导致题目没有明确思路而无从下手．

构造题另一个特点就是形式灵活，变化多样．并不存在一个通用解法或套路可以解决所有构造题，甚至很难找出解题思路的共性．

## 例题

下面将列举一些例题帮助读者体会构造题的一些思想内涵，给予思路上的启发．建议大家深入思考后再查看题解，也欢迎大家参与分享有趣的构造题．

### 例题 1

Codeforces Round #384 (Div. 2) C.Vladik and fractions

构造一组 𝑥,𝑦,𝑧 x,y,z，使得对于给定的 𝑛 n，满足 1 𝑥 +1 𝑦 +1 𝑧 =2 𝑛 1 x+1 y+1 z=2 n

解题思路

从样例二可以看出本题的构造方法．

显然 𝑛,𝑛 +1,𝑛(𝑛 +1)n,n+1,n(n+1) 为一组合法解．特殊地，当 𝑛 =1 n=1 时，无解，这是因为 𝑛 +1 n+1 与 𝑛(𝑛 +1)n(n+1) 此时相等．

至于构造思路是怎么产生的，大概就是观察样例加上一点点数感了吧．此题对于数学直觉较强的人来说并不难．

### 例题 2

Luogu P3599 Koishi Loves Construction

Task1：试判断能否构造并构造一个长度为 𝑛 n 的 1…𝑛 1…n 的排列，满足其 𝑛 n 个前缀和在模 𝑛 n 的意义下互不相同

Task2：试判断能否构造并构造一个长度为 𝑛 n 的 1…𝑛 1…n 的排列，满足其 𝑛 n 个前缀积在模 𝑛 n 的意义下互不相同

解题思路

对于 task1：

当 𝑛 n 为奇数时，无法构造出合法解；

当 𝑛 n 为偶数时，可以构造一个形如 𝑛,1,𝑛 −2,3,⋯n,1,n−2,3,⋯ 这样的数列．

首先，我们可以发现 𝑛 n 必定出现在数列的第一位，否则 𝑛 n 出现前后的两个前缀和必然会陷入模意义下相等的尴尬境地；

然后，我们考虑构造出整个序列的方式：

考虑通过构造前缀和序列的方式来获得原数列，可以发现前缀和序列两两之间的差在模意义下不能相等，因为前缀和序列的差分序列对应着原来的排列．

因此我们尝试以前缀和数列在模意义下为

0,1,−1,2,−2,⋯0,1,−1,2,−2,⋯

这样的形式来构造这个序列，不难发现它完美地满足所有限制条件．

对于 task2：

当 𝑛 n 为除 4 4 以外的合数时，无法构造出合法解

当 𝑛 n 为质数或 4 4 时，可以构造一个形如 1,2 1,3 2,⋯,𝑛−1 𝑛−2,𝑛 1,2 1,3 2,⋯,n−1 n−2,n 这样的数列

先考虑什么时候有解：

显然，当 𝑛 n 为合数时无解．因为对于一个合数来说，存在两个比它小的数 𝑝,𝑞 p,q 使得 𝑝 ×𝑞 ≡0(m o d 𝑛)p×q≡0(mod n)，如 (3 ×6)%9 =0(3×6)%9=0．那么，当 𝑝,𝑞 p,q 均出现过后，数列的前缀积将一直为 0 0，故合数时无解．特殊地，我们可以发现 4 =2 ×2 4=2×2，无满足条件的 𝑝,𝑞 p,q，因此存在合法解．

我们考虑如何构造这个数列：

和 task1 同样的思路，我们发现 1 1 必定出现在数列的第一位，否则 1 1 出现前后的两个前缀积必然相等；而 𝑛 n 必定出现在数列的最后一位，因为 𝑛 n 出现位置后的所有前缀积在模意义下都为 0 0．分析题目给出的几组样例以后发现，所有样例中均有一组合法解满足前缀积在模意义下为 1,2,3,⋯,𝑛 1,2,3,⋯,n，因此我们可以构造出上文所述的数列来满足这个条件．那么我们只需证明这 𝑛 n 个数互不相同即可．

我们发现这些数均为 1⋯𝑛 −2 1⋯n−2 的逆元 +1+1，因此各不相同，此题得解．

### 例题 3

AtCoder Grand Contest 032 B

给定一个整数 𝑁 N，试构造一个节点数为 𝑁 N 无向图．令节点编号为 1…𝑁 1…N，要求其满足以下条件：

- 这是一个简单连通图．
- 存在一个整数 𝑆 S 使得对于任意节点，与其相邻节点的下标和为 𝑆 S．

保证输入数据有解．

解题思路

通过分析 𝑛 =3,4,5 n=3,4,5 的情况，我们可以找到一个构造思路．

构造一个完全 𝑘 k 分图，保证这 𝑘 k 部分和相等．则每个点的 𝑆 S 均相等，为 (𝑘−1)∑𝑛 𝑖=1 𝑖 𝑘(k−1)∑i=1 n i k．

如果 𝑛 n 为偶数，那么我们可以前后两两配对，即 {1,𝑛},{2,𝑛 −1}⋯{1,n},{2,n−1}⋯

如果 𝑛 n 为奇数，那么我们可以把 𝑛 n 单拿出来作为一组，剩余的 𝑛 −1 n−1 个两两配对，即 {𝑛},{1,𝑛 −1},{2,𝑛 −2}⋯{n},{1,n−1},{2,n−2}⋯

这样构造出的图在 𝑛 ≥3 n≥3 时连通性易证，在此不加赘述．

此题得解．

### 例题 4

BZOJ 4971「Lydsy1708 月赛」记忆中的背包

经过一天辛苦的工作，小 Q 进入了梦乡．他脑海中浮现出了刚进大学时学 01 背包的情景，那时还是大一萌新的小 Q 解决了一道简单的 01 背包问题．这个问题是这样的：

给定 𝑛 n 个物品，每个物品的体积分别为 𝑣 1,𝑣 2,…,𝑣 𝑛 v 1,v 2,…,v n，请计算从中选择一些物品（也可以不选），使得总体积恰好为 𝑤 w 的方案数．因为答案可能非常大，你只需要输出答案对 𝑃 P 取模的结果．

因为长期熬夜刷题，他只看到样例输入中的 𝑤 w 和 𝑃 P，以及样例输出是 𝑘 k，看不清到底有几个物品，也看不清每个物品的体积是多少．直到梦醒，小 Q 也没有看清 𝑛 n 和 𝑣 v，请写一个程序，帮助小 Q 一起回忆曾经的样例输入．

解题思路

这道题是自由度最高的构造题之一了．这就导致了没有头绪，难以入手的情况．

首先，不难发现模数是假的．由于我们自由构造数据，我们一定可以让方案数不超过模数．

通过奇怪的方式，我们想到可以通过构造 𝑛 n 个 代价为 1 1 的小物品和几个代价大于 𝑤 2 w 2 的大物品．

由于大物品只能取一件，所以每个代价为 𝑥 x 的大物品对方案数的贡献为 (𝑛 𝑤−𝑥)(n w−x)．

令 𝑓 𝑖,𝑗 f i,j 表示有 𝑖 i 个 1 1，方案数为 𝑗 j 的最小大物品数．

用 dp 预处理出 𝑓 f，通过计算可知只需预处理 𝑖 ≤2 0 i≤20 的所有值即可．

此题得解．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：leoleoasd, Estrella-Explore, Tiphereth-A, yzxoi, Enter-tainer, HeRaNO, iamtwz, ksyx, Marquis03, NachtgeistW, StudyingFather, Xeonacid
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用