你们 IOI 都这么喜欢二合一题的？？？

· · 题解

n=12k

先考虑 2 \mid k 的情况。

考虑把颜色分成四个块，分两种情况构造。

首先构造存在至少两个颜色在同一个块的情况，那么我们建立 6 个子图，每个子图是颜色两两配对之后连出来的完全图，总共花费 6k。

然后考虑三种颜色块都不一样的情况，建立 4 个子图，每个子图包含三个颜色块，因为没有块内边的需求所以块内没有边，然后块间两两连边，每个子图 1.5k，总共 6k。

构造出 $k-1$ 的图，然后构造用 $12$ 操作加入两个点。 直接在第一类图里面每个子图加入两个新颜色的点，两个点之间连边，然后两个点各向子图中的每一个存在的点连边，总共增加了 $12$ 个点。 ### $k=1

两个不同色点连边。

k=2

任意三个颜色建立子图连一个三元环。

k=3, k=4

分成两块，块内加上另一边的每一个点连完全图。

k=5

没构造出来，学习了 qoj 的 ac 代码。

首先构造 5 个子图，每个子图考虑构造几种模意义下的偏移量，使得任意两种偏移量的子图有交。

因为度数限制所以我们把 1 分成 +1 和 -1 考虑，按照奇偶去分一下，即奇数位置和偶数位置取反，1 的符号以奇数点为准。

进行下列构造五个集合：

\{+2,-2,+3,-3,+5\}\\ \{+1,-1,+4,-4,+5\}\\ \{-1,+2,-2,+4,-4\}\\ \{+1,+2,-2,+3,-3\}\\ \{-1,+3,-3,+4,-4\}\\

然后就做完了。