题解：P17244 [IOI 2026] 魔幻之城 / Magic City

· · 题解

这个题到底是谁在会？？

N=14K \pm O(1)

vp 时止步的想法。虽然与正解关系不是很大，但是还是为后面正解的构造提供了一些基本的思考。不感兴趣也可以跳过这一部分。

有一个看起来比较对的构造是直接扔一个点数为 K+1 的完全图，这样记其点集为 S，那么对任意的三元组 (x,y,z)，只要有 \{x,y,z\} \in S，那么就会存在类型分别为 x,y,z 的三点路径。因此，我们只需要构造若干个集合，使其大小 \le K+1，并能覆盖所有三元组即可。

第一个集合显然取 \{1,2,\dots,K+1\}，第二个集合只取剩下的 K-1 个数有点浪费，我们把 1,2 也扔进去，即取 \{1,2,K+2,K+3,\dots,2K\}。现在还缺什么呢？记 A=\{3,4,\dots,K+1\},B=\{K+2,K+3,\dots,2K\},C=\{1,2\}，那么缺少的三元组形如：

先来解决前两种。最初我的想法是采取一个类似分治的策略，将 A,B 均平分为 A_0,A_1,B_0,B_1，然后取所有集合 A_i \cup B_j，剩余的再递归处理（我也不确定这个方案行不行），但是研究一下为什么会剩余某些没有覆盖就会发现，根本原因在于存在 x,y \in A 使得 x,y 没有同时出现在一轮对 A 分出的某个子集中（即上文的 A_0,A_1）。不妨对 A 考虑，现在我们的问题形如：给定一个集合 S，大小为 n，你需要进行若干次划分，每次将其划分为两个大小为 \dfrac{n}{2} 的集合，使得对于任意 x,y \in S 都有一次划分满足 x,y 同时被划分到某个集合。

这个问题容易使用三次划分解决，将 S 平分为四份 S_0,S_1,S_2,S_3，第一次取 (0,1),(2,3)，第二次取 (0,2),(1,3)，第三次取 (0,3),(1,2) 即可。

那么回到原问题，设某一次两边划分出来的两个集合是 A_0,A_1 以及 B_0,B_1，我们只需要构造四个完全图，点集为所有的 A_i \cup B_j 即可。点数为 12K 左右。

再考虑后两种情况：这是简单的，稍加计算会发现我们之前每一轮构造的集合点数都不超过 K，于是只需要在第一轮所有集合中加入一个 1，第二轮加入一个 2 即可。

总的花费点数是 14K \pm O(1)，可以获得约 60 分。

N=12K

我们将点集分块的策略似乎已经很优秀了，但是还是不够。思考一下，对于三元组 (x,y,z)，题目只要求我们在 x,y 以及 y,z 之间存在边，并没有要求在 x,z 之间存在边，而我们构造完全图的想法实际上是加强了这一限制。于是我们想办法将完全图替换为另一种结构。

既然要求 y 与 x,z 均存在边，不妨先来关注一下 y 的邻居。对于一个 y，我们希望其邻居能够覆盖所有剩余的 2K-1 种类型。

现在的问题是，给定一个大小为 2n-1 的集合 S，每次需要选出一个 T \subseteq S，使得每个 x,y \in S 都同时在某次选出的 T 中。由于我们只有 12K 个点，因此需要在 6 次中解决。

第一个集合显然选择 \{1,2,\dots,n\}。为了覆盖尽可能多的未覆盖的二元组，第二个集合应该选择 \{n,n+1,\dots,2n-1\}。发现剩余未覆盖的二组 (x,y) 都形如 x \in \{1,2,\dots,n-1\}，y \in \{n+1,n+2,\dots,2n-1\}。使用类似前面的方法，将两个集合分别平分，再使用四次两两配对即可在 6 次中解决。

关注了单个 y 的情况，我们还需要考虑如何将其组合为一个完整的图。计算对于一个类型 y，需要多少个点连向类型 x 的点，即为 c_{x,y}。不难发现，除了一个点 c_{x,y}=2 以外，其余的 c 值都为 3。由于最终有 2K 种类型，于是构造是简单的：将 0 \sim 2K-1 的类型两两配对，对于一对类型 (a,b)，令 c_{a,b}=c_{b,a}=2，其余均为 3 即可。这样即可构造出一张满足条件的无向图。

这样我们便使用 12K 的点数完成了构造，可以获得 89.74 分。

K=3,4,5

这一部分本质上是对集合覆盖做优化，要求 K=3 使用 4 次，K=5 使用 5 次完成覆盖。首先可以手玩一下 K=3，不难得出如下解：

1 1 0 1 0
1 1 0 0 1
0 0 1 1 1
1 1 1 0 0

其中第 i 行第 j 列为 1 代表第 i 次选择子集时 j 被选，否则不被选。

发现能压缩的主要原因是经过一次选择后某一边只剩下了一个数，就没有必要再花两次的代价来覆盖它了。于是容易得出 K=4,5 的解：

1 1 1 0 0 0 1
0 0 1 0 1 1 1
1 1 0 0 1 1 0
0 0 0 1 1 1 1
1 1 1 1 0 0 0

0 0 0 1 0 1 1 1 1
1 1 1 0 0 0 0 1 1
1 1 1 0 0 1 1 0 0
0 0 0 0 1 1 1 1 1
1 1 1 1 1 0 0 0 0

于是整个问题得到解决。