E. 团划分 详细题解

题目核心理解

给定两个整数 $n$ 和 $k$。有 $n$ 个图上顶点，编号 $1$ 到 $n$。 你需要给每个顶点 $i$ 分配一个互不相同的数值 $a_i$（范围 $1$ 到 $n$）。

连边规则：对任意两点 $i,j$，若满足

则两点之间连边。

要求构造一组 $a_i$，使得这张图能被分成最少数量的团，并输出具体划分方案。 团的定义：集合内任意两点之间都直接连边。

核心思路

1. 关键性质

• 同一个团里的顶点数量不可能超过 $k$。 若同一团内有至少 $k+1$ 个顶点，则必存在两点满足 $|i-j|\ge k$，再加上 $|a_i-a_j|\ge 1$，会使

  $$|i-j|+|a_i-a_j|\ge k+1$$

  两点不连边，矛盾。

• 因此最少团数为

  $$q=\left\lceil \frac{n}{k} \right\rceil$$

2. 构造规则

• 将顶点按顺序每 $k$ 个分为一组，每组构成一个团。
• 对每组大小为 $k$ 的块，构造排列 $a_i$： 设 $m=\left\lceil \dfrac{k}{2} \right\rceil$， 前半部分倒序：$m,m-1,\dots,1$， 后半部分倒序：$k,k-1,\dots,m+1$。
• 该构造能保证块内任意两点满足连边条件，自成一个团。

算法流程

1. 根据 $n$ 和 $k$ 计算最少团数 $q=\left\lceil \dfrac{n}{k} \right\rceil$。
2. 按每 $k$ 个顶点一组，依次划分成团。
3. 对每一组，按“前半倒序、后半倒序”构造 $a_i$。
4. 输出排列 $a$、团数量 $q$、每个点的团编号。

公式与复杂度分析

连边判定：

最少团数：

复杂度

每组测试用例只需要线性构造。 时间复杂度：$O(n)$。 可轻松处理 $n\le 40$、$t\le 1600$ 的数据范围。