构造题目合集

Mr. Panda and Blocks

题目来源：CCPC 2019 总决赛 I 题。

题意

给定 $n$ 种颜色。有 $\frac{n ( n + 1 )}{2}$ 种 $1 \times 1 \times 2$ 的小方块，每个小方块由两个 $n$ 种颜色之一的立方体组成（可能是同一种颜色），且所有小方块之间互不相同。现在要求把这些小方块拼在一起（允许翻转和旋转），使得所有 $n$ 种颜色都是连通的。

值得一提的是，这个题目的样例是这样的：

题解

事实上，没有样例的话这题可能还更好想一点。

Spanning Tree Removal

题目来源：ICPC 2019 上海站 D 题。

题意

给一棵 $n$ 个点的完全图（记为 $K_{n}$ ），要求构造尽可能多地生成树而不重复使用边。

题解

$K_{n}$ 有 $\frac{n ( n - 1 )}{2}$ 条边，每棵生成树需要 $n - 1$ 条，因此最多构造 $⌊ \frac{n}{2} ⌋$ 棵生成树。考虑如何从 $K_{n - 2}$ 递推到 $K_{n}$ 。新增的两个点，与之前的 $n - 2$ 个点之间各有一条边，共计 $2 n - 4$ 条。 $K_{n - 2}$ 有 $⌊ \frac{n}{2} ⌋ - 1$ 棵生成树，为了扩展新增的两个点，需要占用不超过 $n - 2$ 条边，剩下 $n - 2$ 条，以及新增两个点之间的一条，恰好构成一棵新的生成树。

一种方法是按奇偶性构造。假设 $K_{n}$ 的第 $i$ 棵生成树所包含的边的集合为 $T_{n, i}$ ，则：

T_{n, i} = {T_{n - 2, i} \cup {(2 i - 1, n - 1), (2 i, n)} {(2 k - 1, n), (2 k, n - 1) ∣ k ⩽ ⌊ \frac{n}{2} ⌋ - 1} \cup {(n - 1, n)} i ⩽ ⌊ \frac{n}{2} ⌋ - 1 i = ⌊ \frac{n}{2} ⌋

Avoid Prime Sum

题意

要求使用 $1, 2, 3, \dots, n^{2}$ 构造一个 $n \times n$ 的矩阵，满足任意两个相邻（四联通）的数之和不为质数。数据范围： $3 ⩽ n ⩽ 1 0^{3}$ 。

题解

显然，奇数与奇数之和、偶数与偶数之和都不是质数，因此需要处理的就是奇数与偶数相邻的地方。把所有奇数和偶数分别放在矩阵的上下两半，就可以保证仅有 $n$ 个奇数和偶数相邻。当 $n ⩾ 6$ 时，我们能够把相邻的位置全部填上 $3$ 的倍数。至于 $3 ⩽ n ⩽ 5$ 的情况，我们可以手动构造样例。