构造

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

引入

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

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

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

特点

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

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

例题

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

例题 1

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

构造三个两两不同的正整数 \(x,y,z\)，使得对于给定的 \(n\)，满足 \(\dfrac{1}{x}+\dfrac{1}{y}+\dfrac{1}{z}=\dfrac{2}{n}\)．

解题思路

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

可将 \(\dfrac{2}{n}\) 分解为 \(\dfrac{1}{n}+\dfrac{1}{n}\)，再将后一项写为 \(\dfrac{1}{n+1}+\dfrac{1}{n(n+1)}\)．所以 \(n,n+1,n(n+1)\) 即为一组合法解．特别地，\(n=1\) 时无解，因为三个互异正整数的倒数和至多为 \(1+\dfrac{1}{2}+\dfrac{1}{3}<2\)．

例题 2

Luogu P3599 Koishi Loves Construction

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

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

解题思路

两项任务在 \(n=1\) 时均直接取排列 \([1]\)．以下设 \(n>1\)．

对于 Task1：

当 \(n\) 为奇数时，无法构造出合法解；当 \(n\) 为偶数时，可以构造一个形如 \(n,1,n-2,3,\cdots\) 这样的数列．

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

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

考虑通过构造前缀和序列的方式来获得原数列，可以发现相邻前缀和之差（再加第一项）在模意义下应互不相同，因为前缀和序列的差分序列对应着原来的排列．

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

\[ 0,1,-1,2,-2,\cdots \]

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

对于 Task2：

当 \(n\) 为除 \(4\) 以外的合数时，无法构造出合法解；当 \(n=4\) 时单独取 \([1,3,2,4]\)．当 \(n\) 为质数时，可以构造一个形如 \(1,\dfrac{2}{1},\dfrac{3}{2},\cdots,\dfrac{n-1}{n-2},n\) 这样的数列，其中除法表示乘模 \(n\) 的逆元后取 \([1,n]\) 中的代表元．

先考虑什么时候有解：

当 \(n\) 为除 \(4\) 以外的合数时无解．因为对于一个合数来说，存在两个比它小的数 \(p,q\) 使得 \(p\times q \equiv 0 \pmod n\)，如 \((3\times6)\bmod 9=0\)．那么，当 \(p,q\) 均出现过后，数列的前缀积将一直为 \(0\)，故除 \(4\) 以外的合数无解．特殊地，我们可以发现 \(4=2\times 2\)，无满足条件的 \(p,q\)，因此存在合法解．

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

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

我们发现这些数均为 \(1 \cdots n-2\) 的逆元 \(+1\)，因此各不相同，此题得解．

例题 3

AtCoder Grand Contest 032 B

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

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

保证输入数据有解．

解题思路

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

构造一个完全 \(k\) 分图，保证这 \(k\) 部分和相等．则每个点的 \(S\) 均相等，为

\[ S=\dfrac{(k-1)\sum_{i=1}^{n}i}{k}． \]

如果 \(n\) 为偶数，那么我们可以前后两两配对，即 \(\{1,n\},\{2,n-1\}\cdots\)．

如果 \(n\) 为奇数，那么我们可以把 \(n\) 单拿出来作为一组，剩余的 \(n-1\) 个两两配对，即 \(\{n\},\{1,n-1\},\{2,n-2\}\cdots\)．

这样构造出的图在 \(n\ge 3\) 时连通性易证，在此不加赘述．

此题得解．

例题 4

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

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

给定 \(n\) 个物品，每个物品的体积分别为 \(v_1,v_2,\ldots,v_n\)，请计算从中选择一些物品（也可以不选），使得总体积恰好为 \(w\) 的方案数．因为答案可能非常大，你只需要输出答案对 \(P\) 取模的结果．

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

多组数据，数据满足 \(50\le w\le20000\)、\(1\le P\le2^{30}\)、\(0\le k\le\min(20000,P-1)\)；要求输出 \(1\le n\le40\) 个物品，且 \(1\le v_i\le20000\)．

解题思路

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

因为 \(k<P\)，所以我们可以考虑直接构造方案数恰为 \(k\) 的物品集合．

一种构造方式是选取 \(i\) 个体积为 \(1\) 的小物品和若干个体积为 \(w-t\) 的大物品，其中 \(1\le i\le20\)、\(0\le t\le i\)．因为 \(i<w\) 且 \(w-t\ge w-20>w/2\)，恰好装满背包的方案必须选择一个大物品．

令每个体积为 \(w-t\) 的大物品对方案数的贡献为 \(C\)，则 \(C=\dbinom{i}{t}\)，不同大物品的贡献相加．即使体积相同，不同物品仍分别计数．

令 \(f_{i,j}\) 表示有 \(i\) 个 \(1\)，方案数为 \(j\) 的最小大物品数．

固定 \(i\)，令 \(f_{i,0}=0\)，其余状态初值为 \(+\infty\)．按 \(j\) 递增计算完全背包转移：

\[ f_{i,j}=1+\min_{0\le t\le i;~C\le j}f_{i,j-C},\qquad 1\le j\le20000． \]

记录取得最小值的 \(t\)，即可回溯出每个大物品的体积 \(w-t\)．对全部 \(0\le k\le20000\) 计算可得 \(\min_{1\le i\le 20}(i+f_{i,k})\le 29<40\)，所以这段预处理范围足够．

参考实现

#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;
}

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：leoleoasd, yzxoi, Estrella-Explore
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用