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

min_inf · 2026-08-15 00:58:21 · 题解

讲一下我的 N=12K 部分的做法，虽然比较复杂，vp 的时候遗憾没来得及做明白 K=4k+3 的细节。

K=4k

为了方便之后的一些加减法默认 \bmod 2K 意义下。设 d_1=t_2-t_1,d_2=t_3-t_2。

考虑一个 2K 个点的环（当然我们可能没有实际连环的边），我们连接所有 i\leftrightarrow i+d 的边，可以发现 d 和 -d=2K-d 是一样的。

所以我们只需要考虑 1\le d\le K，把 [1,K] 分为四个大小为 k 的组，我们放 \binom 4 2=6 个环，每个环使用两个不同的组作为 d 连边。

每个 d 会对每个点产生 2 的度数，每个环总共使用 2k 个 d，满足最大度数为 K。

K=4k+1

将 K 随意放入一组，可以发现 d=K 只会产生 1 而不是 2 的度数。

K=4k+2

分成一组大小为 k-1 和三组大小为 k，这四个组编号为 0\sim 3，剩下三个长度为 x,y,z。

我们将 x 放入 (0,1),(2,3) 对应的环，y 放入 (0,2)(1,3)，z 放入 (0,3),(1,2)。

但是这样我们还缺少 d_1,d_2 都在 x,y,z 中的情况，我们将 y 放入 (0,1)，z 放入 (0,2)，x 放入 (0,3) 即可（这就是为什么让第一组少一个）。

K=4k+3

分成四组大小为 k 的，剩下三个 x,y,z。

第一步还是和 4k+2 一样，然后我们只剩下了 1 的度数余量。1 的度数只能连一些匹配，考虑在环之间做一些事情。

对于 (0,1),(2,3) 两个环（我们放了 x），设编号为 p_i,q_i，我们连 p_i\leftrightarrow q_{i+y}。同理我们也可以处理 (y,z),(z,x) 的情况。对于 d_1=\pm x，如果 d_2=+y 就把起点设在第一个环上，d_2=-y 就设在第二个环上，所以容易说明是对的。

code