信息学竞赛中构造题的常用解题方法

· · 个人记录

信息学竞赛中构造题的常用解题方法

本文摘自 2021集训队论文 《信息学竞赛中构造题的常用解题方法》。

构造题是近年算法竞赛中常见的一种题目类型。本文对构造题中常见的几个解题方法进行了介绍，包括抽屉原理的运用、 DFS 树的运用、递归法的运用，并给出了例题和讲解。

1 引言

在近年的算法竞赛中，构造题的出现越来越频繁。不同于传统的计数、最优化等问题，构造题只要求选手给出一组满足约束条件的解,而不需要统计解的数量,或是寻找一组 “最优” 的解。然而，由于其模型繁多，涉及图论、数论、字符串等各领域，且常常难以发现，要解决起来并不容易。

2 抽屉原理

抽屉原理，或称为鸽巢原理，是组合数学上一个非常重要的原理。通常的表述是，若将 n 件物品放入 k 个抽屉，则其中一定有一个抽屉包含至少 \lceil\frac{n}{k}\rceil ，也一定有一个抽屉包含至多 \lfloor\frac{n}{k} \rfloor 。

在一些构造题中，常常会要求构造一个权值至少为（或不超过）某一个数的方案。很多时候，可以考虑找出若干个可行的方案，使得它们的权值之和是定值。假设找出了 k 个可行的方案其总权值和为 n ，由抽屉原理，这些方案的最小权值一定不超过 \lfloor\frac{n}{k}\rfloor ，最大的权值至少为 \lceil\frac{n}{k}\rceil 。

2.1 Errich Tac­ Toe

题目链接

题解：

很巧妙的思路 套路 ！

不妨将行列都用 0,1,\cdots ,n-1 编号，将第 r 行 c 列的格子记为 (r,c) 。

我们将所有格子分为 3 类，其中第 i(0\le i<3) 类包含所有 r+c\equiv i \pmod 3 的格子 (r,c) ，不难发现，在一行或一列的连续 3 个格子包含第 0,1,2 类格子各一个。（分组的思想。考虑一行一列上的连续若干个，若把其分为 x 组，那么必然有两个不在同一组内， x 根据题目条件自己设定。）

由此不难想到以下的几种操作方案：

显然这 3 种操作方案都能使得局面变成平局，而它们的操作次数的总和恰好是棋盘中标志的总数 k ，因此其中操作次数最少的方案的操作次数一定不超过 \lfloor \frac{k}{3}\rfloor 。

2.2 Mine Sweeper 2

题意：

扫雷地图是一张 n 行 m 列的网格，其中每个格子是地雷或空地。每个空地会显示一个数字代表与它相邻的雷的数量（两个格子相邻当且仅当它们共用一个顶点或一条边，不在边界上的格子与恰好 8 个格子相邻）。

在一次操作中,你可以将一个地雷改成空地,或将空地改成地雷。

给定两张扫雷地图 A,B​ ，你需要对 A 进行不超过 \lfloor\frac{nm}{2}\rfloor 次操作，使得 A 所有空地上的数字之和等于 B 所有空地上的数字之和。

1\le n,m\le 1000

题解：

我猜到了结论，结果却因为不会证而完美错过；我想到了将A改成B，却没想到真就这么naive 。

注意到一张地图所有空地上的数字之和等于相邻的（地雷、空地）的对数。这就意味着，如果一张地图的所有地雷改成空地，所有空地改成地雷，其所有空地上的数字之和不变。

由此显然有以下两种方案：

由于每个格子只会在恰好一种方案中被修改，这两种方案的操作次数之和为 nm 。因此能取其中较少的一种，操作次数不超过 \lfloor\frac{nm}{2}\rfloor 。

3 DFS 树

在解决一些图上的构造问题时， DFS 树往往有非常大的帮助。

一张图的 DFS 树是在对其进行深度优先遍历时所形成的树结构。建立了 DFS 树后，图上的边可以分成 4 类。

其中，前向边、后向边、横叉边统称为非树边。

在构造题中，通常我们用的是无向图的 DFS 树。如果我们将每条边按照第一次经过时的方向进行定向。则无向图的 DFS 树满足所有非树边都是后向边。这个性质在解题过程中有非常大的用处。

3.1 Ehab's Last Corollary

题意：

给定一张 n 个点 m 条边的无向连通图，以及一个整数 k，你需要

3\le k\le n\le 10^5,n-1\le m\le 2\times 10^5

题解：

我在想啥，求无向图最大独立集等价于求最大团，是 O(3^n) ，NP 问题，直接把题意转化为不可做 。。。

记 l=\lceil\frac{k}{2} \rceil 。

建出图的 DFS 树，考虑每条非树边 (u,v) （正如上文所说，它一定是后向边），如果 |dep_u-dep_v|<k ，则取 (u,v) 加上 v 到 u 的树上路径即为一个长度不超过 k 的简单环。

否则，考虑两种情况：

至此，我们仅用一次 DFS ，在 O(n+m) 的时间内解决了这个问题。

3.2 景点划分

题意：给定一张 n 个点 m 条边的无向连通图，以及三个整数 a, b, c ，满足 a + b + c = n 。你需要将 n 个顶点分成三个集合 A, B, C ，大小分别为 a, b, c ，使得其中至少两个集合是连通的（集合中的任意两个点能只经过该集合内的点互相到达）。有可能无解。

题解： 不妨设 $a\le b\le c$ ，则只需要集合 $A,B$ 连通即可。假设 $A,C$ 是连通的，我们可以通过将 $C$ 中的一些顶点加入 $B$ 中，使得 $C$ 仍然连通且大小变为 $b$ ，这依然是合法的情况。$B,C$ 连通也是一样的。 这时，我们遇到了一些困难，因为有可能无解，而题目并未给出、我们也并未发现有解的条件，非常难以下手。因此我们不妨先来考虑图是一棵树的情况。 当图是一棵树时，集合 $A,B$ 都是其中的子树，因此一定存在一条边，使得 $A,B$ 处于边的两侧。显然，我们只需要找到一条边，使得其两侧较小和较大的子树分别不小于 $a,b$ 即可。注意到一条边两侧较大的子树一定包含重心，我们可以考虑对重心的性质进行一些分析，如果删去重心之后最大的连通块大小小于 $a$ ，则显然无解，否则设这个连通块的大小为 $x$ ，有重心的性质显然有 $x\le n/2$ ，因此删掉这棵子树后还剩下 $n-x\ge n/2$ 。又由于 $b\le n/2$ （因为 $b\le c$ ），因此这棵子树与重心之间的边就是我们要找的边。 回到一般的情况，我们建立图的 DFS 树。找到 DFS 树的重心，设为 $u$ ，记 $u$ 上方的子树大小为 $T$ ， $u$ 下方的子树为 $S_1,S_2,\cdots ,S_k$ 。考虑几种情况： - 如果 $T$ 或某个 $S_i$ 的大小不小于 $a$ ，则我们可以用和树一样的方法构造一组解。 - 如果 $T$ 和所有 $S_i$ 的大小都小于 $a$ ，我们就需要考虑无向图 DFS 树的性质。不同的 $S_i$ 之间是没有边相连的，同时有一些 $S_i$ 与 $T$ 相连。如果所有与 $T$ 相连的 $S_i$ 加上 $T$ 的大小之和小于 $a$ ，则一定是无解的，因为这表示集合 $A,B$ 都必须包含重心 $u$ 。从 $T$ 开始，我们依次加入与 $T$ 相邻的 $S_i$ ，直到其大小不小于 $a$ 。设得到的点集为 $X$ ，则 $X$ 是连通，我们可以在其中选出 $A$ 。同时由于 $T$ 和 $S_i$ 都是小于 $a$ 的，所以 $X$ 的大小不超过 $2a$ 。因为 $b=n-a-c\le n-2a$ ，因此剩余的点数足够我们选出集合 $B$ 。 至此，我们在 $O(n+m)$ 的时间内完成构造。 ## 4 递归法 在一些构造题中，对于不同的输入，问题的结构有很大的相似性。在很多时候，我们的构造也具有很大的相似性，或是具有周期性。这时，我们往往可以通过递归的方式，对子问题进行构造，并在子问题的构造的基础上进行一些小的微调。来得到原问题的构造。 需要指出的是，递归可以作为一个思想，但在实际解题过程中可能有代码时空复杂度高的缺点，需要选手灵活运用。 **4.1 Baggage** 题意： 有 $2n$ 个包裹，其中有 $n$ 个 $A$ 类包裹，和 $n$ 个 $B$ 类包裹，初始时它们的排列如下： $B\, A \,B\, A\, B\, A \cdots B\, A

这些包裹占据了编号为 1 到 2n 的格子，同时还有编号为 −2n + 1 到 0 的 2n 个空格子可供使用。现在要将这些包裹重新排列,使得它们形如A\, A ... A\, B ... B\, B​ 即,这些包裹占据了相邻的 2n 个格子 （不一定是 1 到 2n ），且所有的 A 类包裹在所有的 B 类包裹的左边。

排列过程由若干次操作组成,在每一次操作中，可以选择相邻的两个包裹 （不能只选择 一个），并将它们移动至某两个相邻的空格中。

给定 n ，找到一个最短的操作序列。

题解：这种要求最优方案的题往往两个步骤：证明下界；构造下界。 与通常构造题不同，本题要求的是最短的操作序列，看起来难以下手。但经过一些尝试，或是对 $n$ 较小的情况进行搜索，会发现它们的最短序列的长度都是 $n$ 。 事实上，证明最操作数次数不少于 $n$​ 是容易的：考虑有多少对相邻的包裹类型相同，设这个个数是 $d$ ，初始时 $d=0$ ，而在结束局面中 $d=2n-2$ 。在一次操作中，取出包裹时不会使 $d$ 增加，而在放回包裹时，假设放的位置是 $t$ 和 $t+1$ ，则只可能增加 $(t-1,t)$ 和 $(t+1,t+2)$ 这两对相邻的包裹。同时容易发现，第一次操作至多使得 $d$ 增加 $1$ ，因此总的操作次数不少于 $1+\lceil\frac{2n-3}{2}\rceil$ 。 接下来，我们就要尝试对所有 $n$ 构造长度为 $n$ 的操作序列。对于 $n$ 较小的情况，我们可以直接利用搜索求出操作序列。经过观察发现，在 $n>3$ 的情形中，我们都是将这些包裹从 $1\sim 2n$ 的格子移植编号为 $-1$ 到 $2n-2$ 的格子。 因此，我们可以定义函数 $solve(n,x)$ 表示将 $x+1$ 到 $x+2n$ 的格子（这些包裹形如 $BABABA\cdots BA$ ）移植编号为 $x-1$ 到 $x+2n-2$ 的格子，并排列成 $AA\cdots AB\cdots BB$ 。 通过尝试，或是对 $n$ 稍大一些的情形的观察，对于 $n\ge 8$​ 的情况，我们可以构造如下操作序列（其中 _ 表示空格子）： ![](https://cdn.luogu.com.cn/upload/image_hosting/ryc007u1.png) 在这里我们发现最后一行的红色部分正好符合 solve 函数的输入，因此我们调用 solve(n-4,x+4) 对其进行递归求解。 ![](https://cdn.luogu.com.cn/upload/image_hosting/hsnygws7.png) 至此，我们便完成了长度为 $n$ 的操作序列的构造，解决了此题。 其实递归法很多时候不会是一次做到位的，有可能前面先做一些，可能还没到达终态，但是找到子问题先递归下去，然后再在回溯的时候变成终态就可以了。 也就说我们要只要找到一种到达子任务的方法，然后再把再找到子任务的区间变成终态后，该区间怎么变成终态的方法，最后考虑基底就可以了。（这应该是一般的解题思路和方法。） **4.2 Strange Housing** 题意： 给定一张 $n$ 个点 $m$ 条边的无向图，你需要选择一个点集 $S$ ，满足： - 一条边 $(u,v)$ 是开启的当且仅当 $u\in S$ 或 $v\in S$ ，则任意一对点都能只经过开启的边互相到达。 - 不存在一条边满足 $u\in S$ 且 $v\in S$ 。 有可能无解。 $2\le n\le 3\times 10^5,0\le m\le 3\times 10^5$ 。 题解： 显然若图不连通则无解。 考虑归纳法证明，假设对于一张连通图都有解。考虑已经有一张可连通的图，加入第 $n$ 个点是否仍然连通。 不难发现，若 $n$ 所连的点有被加入点集的，那么 $n$ 就可以同这个点而和剩下 $n-1$ 个点连通；若 $n$ 所连的点没有被加入点集的，那么 $n$ 自己加入点集就可以了。 这样构造的话要考虑连通性。即每次加入一个点要保证前面的点的都连通。考虑直接上 dfs 一遍，根据 dfs 序的性质每次都是连通图再加上一个点。