第 48 章　构造¶

配套例题：BISHI26 构造 C 的歪、BISHI27 构造数对、BISHI28 构造数独、 BISHI29 小红的排列构造①、BISHI37 数位差与数值和的构造、BISHI38 有向二分图构造来源：无固定课件来源，本章从题单中的六道构造题归纳套路

构造题的特征很鲜明：答案不唯一，只要给出任意一个合法方案即可。它不考数据结构，也很少考复杂度，考的是「能不能想出一个足够简单的方案」。

构造题的核心心法： 不要试图理解题目允许的全部合法方案，只要找到最好写的那一种。

因此构造题的时间几乎全花在纸上，代码往往只有三五行。

48.1　六个通用套路¶

套路	做法	典型题
① 打小表找规律	手算 \(n = 1,2,3,4,5\)，观察	几乎所有构造题的第一步
② 极端化 / 对称化	全填同一个值、只用对角线、首尾配对	BISHI28 构造数独
③ 从平凡解出发做局部修补	先给一个几乎对的解，只修不满足的地方	BISHI29 排列构造
④ 按位 / 按维独立处理	把整体拆成互不影响的小块	BISHI37 数位构造
⑤ 概率法 / 期望论证	证明「随机方案的期望已达标」⟹ 存在解	BISHI38 二分图构造
⑥ 数据规模小就暴力	\(n \le 100\) 时直接枚举全部候选	BISHI27 构造数对

套路②：极端化——构造题最有用的一条¶

出题人给的样例往往「花里胡哨」（每个格子都非零、每个数都不同）， 那是障眼法。真正好写的构造几乎总是最极端的那个：

需求	花哨解	极端解
每行每列和都是 \(k\)	随便填一个魔方阵	主对角线填 \(k\)，其余填 0
构造和为 \(S\) 的 \(n\) 个正整数	随机拆	\(1, 1, \ldots, 1, S-n+1\)
构造两两不同的 \(n\) 个数	随机	\(1, 2, \ldots, n\)
构造一棵树	随机形态	菊花图或链

看到样例复杂，先怀疑它是在误导你。

套路③：从平凡解出发做局部修补¶

先写下最自然的候选（恒等排列 \(a_i = i\)、全 0 矩阵、原串不动），检查它在哪些位置不满足条件，只修那几个位置。 BISHI29 就是「恒等排列只有一处不合法，换两个元素即可」。

套路⑤：概率法¶

若能证明「随机方案的期望已经达到（或超过）要求」，那么必然存在一个不差于期望的具体方案。这一步只用来说明「题目一定有解」，真正的构造还得靠爬山、局部调整或直接找到显式方案。BISHI38 是这个套路的完整演示。

48.2　构造题的三条纪律¶

一、先判无解¶

构造题常常有小规模的无解情形，而它们几乎总是出现在 \(n = 1, 2\)：

题	无解条件
BISHI27 构造数对	\(x = 1\)
BISHI29 排列构造	\(n \le 2\)（\(n = 2\) 也无解，很容易只判 \(n=1\)）

写完构造先手算 \(n = 1\) 和 \(n = 2\)。 这两个值是构造题的失分重灾区。

二、方案不唯一 = special judge¶

样例给的答案和你的不一样完全正常。本地自测时必须自己写校验器（真的去验证方案满足所有条件），不能逐字符比对。本教程为这类题准备了 solutions/_spj/<题号>.py，见 20-输入输出处理的 special judge 一节。

三、输出规模要估算¶

构造题的输出常常是 \(O(n^2)\) 的矩阵。\(n = 10^3\) 时有 \(10^6\) 个数， 逐个 print 必然 TLE：

sys.stdout.write("\n".join(rows) + "\n")     # 每行先拼成字符串，最后一次写出

甚至可以用字符串重复直接拼行，见 BISHI28。

48.3　例题¶

BISHI26　构造 C 的歪（入门）¶

给整数 \(a, b\ (1 \le a,b \le 10^6)\)，求 \(c\) 使 \(\{a,b,c\}\) 排序后成等差数列。题面见 BISHI26 原题（牛客）。

三个数排序后 \(x \le y \le z\) 成等差 \(\iff x + z = 2y\)。给定两个数，第三个有三种放法：

\(c\) 放在	公式	是否恒有解
最大	\(c = 2\max - \min\)	✅ 恒有解且恒为正
最小	\(c = 2\min - \max\)	可能是负数
中间	\(c = (a+b)/2\)	只在 \(a+b\) 为偶数时可行

选恒有解的那一种，题就结束了——这就是 48.1 套路②：

import sys

a, b = map(int, sys.stdin.buffer.read().split()[:2])
# 三个数排序后成等差 <=> 首 + 末 = 2 * 中。把 c 放在最大处最省心：
# min, max, 2*max-min 的公差恒为 max-min >= 0，对 a == b 也成立，且结果恒为正
print(2 * max(a, b) - min(a, b))

\(a = b\) 时 \(c = a\)，三数全等，公差为 0 的等差数列，合法。
别用 (a+b)//2 偷懒：\(a+b\) 为奇数时它是错的。
答案不唯一（样例对同一组输入给出了 1 和 4 两个答案），必须 special judge。

题解见 solutions/BISHI26.py。

BISHI27　构造数对（简单）¶

给 \(x \le 100\)，构造 \((a,b)\) 满足：\(1 \le a,b \le x\)、\(b \mid a\)、\(a\cdot b > x\)、\(a/b < x\)；无解输出 \(-1\)。题面见 BISHI27 原题（牛客）。

\(x \le 100\)——直接 \(O(x^2)\) 暴力枚举（套路⑥）。这是「数据规模决定做法」的教科书例子：

import sys


def main():
    x = int(sys.stdin.buffer.read().split()[0])
    # x <= 100，O(x^2) 暴力枚举足够；推公式反而更容易在边界上翻车
    for b in range(1, x + 1):
        for a in range(b, x + 1, b):        # 从 b 起按步长 b 枚举，自动满足 b | a
            # 条件 3 是严格大于、条件 4 是严格小于，等号一律不取
            if a * b > x and a // b < x:
                print(a, b)                 # 找到任意一组即可，答案不唯一
                return
    print(-1)                               # 只有 x == 1 会走到这里


main()

顺带说规律：取 \(a = b = x\) 时三个条件分别是 \(b \mid a\) ✅、\(x^2 > x\)（\(x>1\)）、 \(1 < x\)（\(x>1\)）。所以 \(x \ge 2\) 时 \((x,x)\) 恒为解，\(x = 1\) 时无解。

代码里仍然写暴力，一是给上面的推论做自检，二是避免推错。 能暴力的时候，别为了「优雅」去推公式——推错的代价远大于多写两行循环。

range(b, x+1, b) 直接按倍数枚举，省掉 a % b == 0 的判断。
条件 3 是严格大于、条件 4 是严格小于，边界写错就在 \(x=1\) 上翻车。

题解见 solutions/BISHI27.py。

BISHI28　构造数独（简单）¶

构造 \(n\times n\ (n \le 10^3)\) 的非负整数矩阵，使每行和、每列和都等于 \(k \le 10^9\)。题面见 BISHI28 原题（牛客）。

套路②极端化的最佳示范：主对角线全填 \(k\)，其余填 0。第 \(i\) 行只有 \(B_{i,i} = k\)，行和 \(= k\)；第 \(j\) 列同理。对任意 \(n \ge 1\)、\(k \ge 1\) 都成立，所以 \(-1\) 是永远不会输出的分支。

import sys

n, k = map(int, sys.stdin.buffer.read().split()[:2])
ks = str(k)
# 主对角线填 k、其余填 0：第 i 行只有第 i 列非零，行和与列和都恰好是 k
# 第 i 行：i 个 0，一个 k，n-1-i 个 0；空格靠字符串重复拼出来，每行只有 O(1) 次 Python 操作
rows = ["0 " * i + ks + " 0" * (n - 1 - i) for i in range(n)]
# n = 1 时两段重复都是空串，结果正好是单个 "k"
sys.stdout.write("\n".join(rows) + "\n")   # 1e6 个元素，必须一次写出

三个要点：

别照抄样例那种「每格都非零」的花式矩阵。样例是障眼法。
\(n = 10^3\) 时矩阵有 \(10^6\) 个元素，输出量约 2 MB。用字符串重复 "0 " * i 直接拼行，每行只有 \(O(1)\) 次 Python 操作，再一次性 "\n".join 写出。逐元素 print 在这里是灾难。
\(n = 1\) 要能正确退化："0 " * 0 + ks + " 0" * 0 = "k"，正确。

题解见 solutions/BISHI28.py。

BISHI29　小红的排列构造①（简单）¶

构造长为 \(n \le 10^5\) 的排列，使所有 \(a_i + i\) 都不是质数；无解输出 \(-1\)。题面见 BISHI29 原题（牛客）。

套路③：从平凡解出发修补。

先试恒等排列 \(a_i = i\)，此时 \(a_i + i = 2i\)。偶数只要大于 2 就一定是合数，所以唯一的破绽是 \(i = 1\)（\(2i = 2\) 是质数）。只需修掉这一处：

把位置 1 和位置 3 的值互换，得到 \(a = [3, 2, 1, 4, 5, \ldots, n]\)：

\(i\)	\(a_i + i\)	是否合数
1	\(3+1 = 4\)	✅
2	\(2+2 = 4\)	✅
3	\(1+3 = 4\)	✅
\(\ge 4\)	\(2i \ge 8\)	✅

import sys

n = int(sys.stdin.buffer.read().split()[0])
if n <= 2:
    print(-1)                         # n = 1 与 n = 2 都无解，只判 n = 1 是本题最高频的 WA
else:
    a = list(range(1, n + 1))         # 先取恒等排列，此时 a_i + i = 2i 全是偶数
    # 唯一的破绽是 i = 1（2i = 2 是质数）；交换位置 1 和位置 3 后这三处都变成 4
    a[0], a[2] = a[2], a[0]           # 列表下标 0 和 2 即题面的位置 1 和 3
    sys.stdout.write(" ".join(map(str, a)) + "\n")

无解判定（48.2 纪律一）：

\(n = 1\)：只有 \([1]\)，\(1+1 = 2\) 是质数 → 无解；
\(n = 2\)：\([1,2] \to 2, 4\)（2 是质数）；\([2,1] \to 3, 3\)（3 是质数）→ 也无解。

只判 \(n = 1\) 就交上去是本题最高频的 WA。 交换需要 \(n \ge 3\)，而 \(n = 3\) 恰好给出 \([3,2,1]\)，边界严丝合缝。

完全不需要筛质数：构造保证了 \(a_i + i\) 恒为 \(\ge 4\) 的偶数。看到「质数」就去写埃氏筛是典型的过度设计。
输出用 " ".join，\(10^5\) 个数逐个 print 会 TLE。

题解见 solutions/BISHI29.py。

BISHI37　数位差与数值和的构造（简单）¶

给 \(n \le 10^9\)，求非负整数 \(x, y\) 使 \(x + y = n\) 且两者数字和之差的绝对值 \(\le 1\)。 \(t \le 10^4\) 组。题面见 BISHI37 原题（牛客）。

关键观察（套路④，按位独立）：只要拆分不产生进位，数字和就是可加的。

把 \(n\) 写成十进制 \(d_{k-1}\cdots d_0\)，对每一位取 \(p_i + q_i = d_i\)（\(0 \le p_i,q_i \le 9\)），则 \(x = \sum p_i 10^i\)、\(y = \sum q_i 10^i\) 满足 \(x+y = n\)，且

\[\operatorname{digitsum}(x) + \operatorname{digitsum}(y) = \sum d_i = S\]

于是问题变成「把 \(S\) 劈成两半」：目标 \(t = \lfloor S/2 \rfloor\)，从高位到低位贪心，每位尽量多分给 \(x\)。最终两者数字和之差 \(= S \bmod 2 \le 1\)。 这同时也证明了题面那句「解一定存在」。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for i in range(1, t + 1):                 # 每组一个数，token 下标与组号一致
        s = data[i]
        digits = [c - 48 for c in s]          # bytes 逐字节得到 ASCII 码，减 '0' 即数值
        need = sum(digits) // 2               # x 要拿走的数字和，下取整使两者之差 <= 1
        xd = []
        for d in digits:                      # 从高位到低位贪心，每位尽量多分给 x
            take = d if d <= need else need   # 不超过本位数值，也不超过剩余配额
            need -= take
            xd.append(take)
        # 逐位拆分且每位都满足 p+q = d，不会产生进位，数字和因此可加
        x = int("".join(map(str, xd)))        # 转成 int 顺带去掉可能的前导零
        out.append("%d %d" % (x, int(s) - x))   # y = n - x，各位恰好是 d - take，非负
    sys.stdout.write("\n".join(out) + "\n")


main()

四个要点：

必须按「无进位拆分」做。随便找个 \(x\) 再算 \(y = n - x\) 会产生借位，数字和的可加性立刻失效。
\(y\) 允许为 0（题面说的是非负整数）。
\(x\) 的高位可能是 0（如 \(n = 1206\) 得 \(x = 1201\)、\(y = 0005\)），转成 int 输出即可，不能带前导零。
\(n \le 10^9\) 最多 10 位，每组 \(O(10)\)；枚举 \(x\) 是 \(10^9\) 次，想都别想。

题解见 solutions/BISHI37.py。

BISHI38　有向二分图构造（简单）¶

\(N \le 10^5\) 点、\(M \le 2\times10^5\) 边的有向图，给每个点染黑或白。「起点黑、终点白」的边称为核心边。要求核心边数 \(\ge \lfloor M/4 \rfloor + 1\)，并输出所有核心边的编号。题面见 BISHI38 原题（牛客）。

第一步：用概率法说明阈值一定能达到（套路⑤）。每个点独立等概率染黑/白，则每条边成为核心边的概率是 \(\frac12 \times \frac12 = \frac14\)，

\[\mathbb{E}[\text{核心边数}] = \frac{M}{4}\]

核心边数是整数，而全黑染色给出 \(0 < M/4\)（\(M \ge 1\)），说明它不是常数，于是必然存在某种染色使核心边数严格大于 \(M/4\)。而「整数 \(> M/4\)」正是「\(\ge \lfloor M/4\rfloor + 1\)」。

第二步：把它构造出来——局部搜索（爬山）。

记 \(\mathrm{outW}(v)\) 为 \(v\) 指向白点的出边数，\(\mathrm{inB}(v)\) 为黑点指向 \(v\) 的入边数。因为无自环，翻转 \(v\) 的颜色只影响与 \(v\) 相邻的边：

\(v\) 当前颜色	翻转后核心边数的增量
黑 → 白	\(\mathrm{inB}(v) - \mathrm{outW}(v)\)
白 → 黑	\(\mathrm{outW}(v) - \mathrm{inB}(v)\)

维护一个待检查队列，只要某点翻转能严格增加答案就翻，并把受影响的邻居重新入队。每次翻转答案至少 \(+1\)，上界是 \(M\)，所以一定终止。

第三步：整体取反这一招不能少。 单点翻转对「所有边都是白→黑」这类局面无能为力，而整体取反一步就翻盘（取反后的核心边数 = 原来的「白→黑」边数）。

初始解取「出度 \(\ge\) 入度就染黑」——出度大的点当源、入度大的点当汇，起点质量高，通常一两轮就远超阈值；极端情况再做几次固定种子的随机重启（保证可复现）。

完整代码见 solutions/BISHI38.py。

四个要点：

阈值是严格大于 \(M/4\)，所以「随机一次取期望值」不够，必须爬山推过去。
图有重边（题面明说不保证无重边），所有统计必须按边而不是点对来算。
输出的是核心边的编号（按输入顺序 \(1..M\)），不是端点。
随机种子要固定：同一输入多次运行结果必须一致，否则调试无从下手。

这题是全章唯一需要「算法」的构造题。它演示了构造题的完整方法论： 先证明解存在（概率法），再设计一个必然收敛的搜索把它找出来。

48.4　本章速查¶

套路	关键动作
打小表	手算 \(n=1..5\) 找规律
极端化	对角线 / 全同 / 菊花图 / \(1,2,\ldots,n\)
局部修补	从平凡解出发，只修不满足的位置
按位独立	十进制 / 二进制逐位处理，避免进位
概率法	期望达标 ⟹ 存在解
暴力	\(n \le 100\) 就 \(O(n^2)\) 枚举

纪律	内容
先判无解	重点手算 \(n=1\) 和 \(n=2\)
special judge	输出与样例不同是正常的，本地要自写校验器
输出规模	\(O(n^2)\) 输出必须 `"\n".join` 一次写出
别过度设计	「不是质数」不等于要筛质数
别信样例	样例的花哨方案通常是障眼法

题	一句话解法
BISHI26	\(c = 2\max - \min\)
BISHI27	\(x\le100\) 暴力；规律是 \(x\ge2\) 时 \((x,x)\)
BISHI28	主对角线填 \(k\)，其余 0
BISHI29	恒等排列交换位置 1 和 3；\(n\le2\) 无解
BISHI37	无进位逐位拆分，把数字和劈成两半
BISHI38	概率法证存在 + 局部搜索 + 整体取反

第 48 章 构造¶

48.1 六个通用套路¶

套路②：极端化——构造题最有用的一条¶

套路③：从平凡解出发做局部修补¶

套路⑤：概率法¶

48.2 构造题的三条纪律¶

一、先判无解¶

二、方案不唯一 = special judge¶

三、输出规模要估算¶

48.3 例题¶

BISHI26 构造 C 的歪（入门）¶

BISHI27 构造数对（简单）¶

BISHI28 构造数独（简单）¶

BISHI29 小红的排列构造①（简单）¶

BISHI37 数位差与数值和的构造（简单）¶

BISHI38 有向二分图构造（简单）¶

48.4 本章速查¶