构造
本页面将简要介绍构造题这类题型．
引入
构造题是比赛中常见的一类题型．
从形式上来看，问题的答案往往具有某种规律性，使得在问题规模迅速增大的时候，仍然有机会比较容易地得到答案．
这要求解题时要思考问题规模增长对答案的影响，这种影响是否可以推广．例如，在设计动态规划方法的时候，要考虑从一个状态到后继状态的转移会造成什么影响．
特点
构造题一个很显著的特点就是高自由度，也就是说一道题的构造方式可能有很多种，但是会有一种较为简单的构造方式满足题意．看起来是放宽了要求，让题目变得简单了，但很多时候，正是这种高自由度导致题目没有明确思路而无从下手．
构造题另一个特点就是形式灵活，变化多样．并不存在一个通用解法或套路可以解决所有构造题，甚至很难找出解题思路的共性．
例题
下面将列举一些例题帮助读者体会构造题的一些思想内涵，给予思路上的启发．建议大家深入思考后再查看题解，也欢迎大家参与分享有趣的构造题．
例题 1
Codeforces Round #384 (Div. 2) C.Vladik and fractions
构造三个两两不同的正整数 𝑥,𝑦,𝑧
，使得对于给定的 𝑛，满足 1𝑥 +1𝑦 +1𝑧 =2𝑛．
解题思路
从样例二可以看出本题的构造方法．
可将 2𝑛 分解为 1𝑛 +1𝑛，再将后一项写为 1𝑛+1 +1𝑛(𝑛+1)．所以 𝑛,𝑛 +1,𝑛(𝑛 +1) 即为一组合法解．特别地，𝑛 =1 时无解，因为三个互异正整数的倒数和至多为 1 +12 +13 <2．
例题 2
Luogu P3599 Koishi Loves Construction
Task1：试判断能否构造并构造一个长度为 𝑛 的 1…𝑛 的排列，满足其 𝑛 个前缀和在模 𝑛 的意义下互不相同．
Task2：试判断能否构造并构造一个长度为 𝑛 的 1…𝑛 的排列，满足其 𝑛 个前缀积在模 𝑛 的意义下互不相同．
解题思路
两项任务在 𝑛 =1 时均直接取排列 [1]．以下设 𝑛 >1．
对于 Task1：
当 𝑛 为奇数时，无法构造出合法解；当 𝑛 为偶数时，可以构造一个形如 𝑛,1,𝑛 −2,3,⋯ 这样的数列．
首先，我们可以发现 𝑛 必定出现在数列的第一位，否则 𝑛 出现前后的两个前缀和必然会陷入模意义下相等的尴尬境地；
然后，我们考虑构造出整个序列的方式：
考虑通过构造前缀和序列的方式来获得原数列，可以发现相邻前缀和之差（再加第一项）在模意义下应互不相同，因为前缀和序列的差分序列对应着原来的排列．
因此我们尝试以前缀和数列在模意义下为
0,1,−1,2,−2,⋯ 这样的形式来构造这个序列，不难发现它完美地满足所有限制条件．
对于 Task2：
当 𝑛 为除 4 以外的合数时，无法构造出合法解；当 𝑛 =4 时单独取 [1,3,2,4]．当 𝑛 为质数时，可以构造一个形如 1,21,32,⋯,𝑛−1𝑛−2,𝑛 这样的数列，其中除法表示乘模 𝑛 的 逆元 后取 [1,𝑛] 中的代表元．
先考虑什么时候有解：
当 𝑛 为除 4 以外的合数时无解．因为对于一个合数来说，存在两个比它小的数 𝑝,𝑞 使得 𝑝 ×𝑞 ≡0(mod𝑛)，如 (3 ×6)mod9 =0．那么，当 𝑝,𝑞 均出现过后，数列的前缀积将一直为 0，故除 4 以外的合数无解．特殊地，我们可以发现 4 =2 ×2，无满足条件的 𝑝,𝑞，因此存在合法解．
我们考虑如何构造这个数列：
和 task1 同样的思路，我们发现 1 必定出现在数列的第一位，否则 1 出现前后的两个前缀积必然相等；而 𝑛 必定出现在数列的最后一位，因为 𝑛 出现位置后的所有前缀积在模意义下都为 0．分析题目给出的几组样例以后发现，所有样例中均有一组合法解满足前缀积在模意义下为 1,2,3,⋯,𝑛，因此我们可以构造出上文所述的数列来满足这个条件．那么我们只需证明这 𝑛 个数互不相同即可．
我们发现这些数均为 1⋯𝑛 −2 的逆元 +1，因此各不相同，此题得解．
例题 3
AtCoder Grand Contest 032 B
给定一个整数 𝑁，试构造一个节点数为 𝑁 的无向图．令节点编号为 1…𝑁，要求其满足以下条件：
- 这是一个简单连通图．
- 存在一个整数 𝑆 使得对于任意节点，与其相邻节点的下标和为 𝑆．
保证输入数据有解．
解题思路
通过分析 𝑛 =3,4,5 的情况，我们可以找到一个构造思路．
构造一个完全 𝑘 分图，保证这 𝑘 部分和相等．则每个点的 𝑆 均相等，为
𝑆=(𝑘−1)∑𝑛𝑖=1𝑖𝑘． 如果 𝑛 为偶数，那么我们可以前后两两配对，即 {1,𝑛},{2,𝑛 −1}⋯．
如果 𝑛 为奇数，那么我们可以把 𝑛 单拿出来作为一组，剩余的 𝑛 −1 个两两配对，即 {𝑛},{1,𝑛 −1},{2,𝑛 −2}⋯．
这样构造出的图在 𝑛 ≥3 时连通性易证，在此不加赘述．
此题得解．
例题 4
BZOJ 4971「Lydsy1708 月赛」记忆中的背包
经过一天辛苦的工作，小 Q 进入了梦乡．他脑海中浮现出了刚进大学时学 01 背包的情景，那时还是大一萌新的小 Q 解决了一道简单的 01 背包问题．这个问题是这样的：
给定 𝑛 个物品，每个物品的体积分别为 𝑣1,𝑣2,…,𝑣𝑛，请计算从中选择一些物品（也可以不选），使得总体积恰好为 𝑤 的方案数．因为答案可能非常大，你只需要输出答案对 𝑃 取模的结果．
因为长期熬夜刷题，他只看到样例输入中的 𝑤 和 𝑃，以及样例输出是 𝑘，看不清到底有几个物品，也看不清每个物品的体积是多少．直到梦醒，小 Q 也没有看清 𝑛 和 𝑣，请写一个程序，帮助小 Q 一起回忆曾经的样例输入．
多组数据，数据满足 50 ≤𝑤 ≤20000、1 ≤𝑃 ≤230、0 ≤𝑘 ≤min(20000,𝑃 −1)；要求输出 1 ≤𝑛 ≤40 个物品，且 1 ≤𝑣𝑖 ≤20000．
解题思路
这道题是自由度最高的构造题之一了．这就导致了没有头绪，难以入手的情况．
因为 𝑘 <𝑃，所以我们可以考虑直接构造方案数恰为 𝑘 的物品集合．
一种构造方式是选取 𝑖 个体积为 1 的小物品和若干个体积为 𝑤 −𝑡 的大物品，其中 1 ≤𝑖 ≤20、0 ≤𝑡 ≤𝑖．因为 𝑖 <𝑤 且 𝑤 −𝑡 ≥𝑤 −20 >𝑤/2，恰好装满背包的方案必须选择一个大物品．
令每个体积为 𝑤 −𝑡 的大物品对方案数的贡献为 𝐶，则 𝐶 =(𝑖𝑡)，不同大物品的贡献相加．即使体积相同，不同物品仍分别计数．
令 𝑓𝑖,𝑗 表示有 𝑖 个 1，方案数为 𝑗 的最小大物品数．
固定 𝑖，令 𝑓𝑖,0 =0，其余状态初值为 +∞．按 𝑗 递增计算完全背包转移：
𝑓𝑖,𝑗=1+min0≤𝑡≤𝑖; 𝐶≤𝑗𝑓𝑖,𝑗−𝐶,1≤𝑗≤20000． 记录取得最小值的 𝑡，即可回溯出每个大物品的体积 𝑤 −𝑡．对全部 0 ≤𝑘 ≤20000 计算可得 min1≤𝑖≤20(𝑖 +𝑓𝑖,𝑘) ≤29 <40，所以这段预处理范围足够．
参考实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 | #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
constexpr int K = 20000;
constexpr int INF = K + 100;
int c[21][21], take[21][K + 1];
int f[K + 1], best[K + 1], small[K + 1];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
fill(best, best + K + 1, INF);
c[0][0] = 1;
for (int i = 1; i <= 20; ++i) {
c[i][0] = c[i][i] = 1;
for (int t = 1; t < i; ++t) c[i][t] = c[i - 1][t - 1] + c[i - 1][t];
fill(f, f + K + 1, INF);
f[0] = 0;
// 每个大物品贡献 c[i][t] 种方案，按完全背包求最少物品数。
for (int t = 0; t <= i; ++t) {
for (int j = c[i][t]; j <= K; ++j) {
if (f[j - c[i][t]] + 1 < f[j]) {
f[j] = f[j - c[i][t]] + 1;
take[i][j] = t;
}
}
}
for (int k = 0; k <= K; ++k) {
if (i + f[k] < best[k]) {
best[k] = i + f[k];
small[k] = i;
}
}
}
int T;
cin >> T;
while (T--) {
int w, P, k;
cin >> w >> P >> k;
int i = small[k];
vector<int> volumes(i, 1);
// 构造恰好 k 种方案；由于 k < P，无需另外处理取模。
while (k > 0) {
int t = take[i][k];
volumes.push_back(w - t);
k -= c[i][t];
}
cout << volumes.size() << '\n';
for (size_t j = 0; j < volumes.size(); ++j)
cout << volumes[j] << (j + 1 == volumes.size() ? '\n' : ' ');
}
return 0;
}
|
本页面最近更新：2026/9/28 01:09:54，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：leoleoasd, Tiphereth-A, Estrella-Explore, yzxoi, c-forrest, Enter-tainer, HeRaNO, iamtwz, ksyx, Marquis03, NachtgeistW, StudyingFather, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用