自动搬运

查看原文

来自洛谷，原作者为

	wlzhouzhuan 一直在路上。

搬运于2025-08-24 22:24:43，当前版本为作者最后更新于2020-10-20 13:49:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

洛谷 P6865 染色

给定一张无向图，将 $n$ 个节点分成 $k$ 组，使得组内点对间无连边。最小化 $k$ 。

$\texttt{ 01.in, 01.out }$

数据满足 $n=5,m=7,k=3$ ，手玩即可。

$\texttt{ 02.in, 02.out }$

数据满足 $n=10,m=20,k=3$ ，手玩即可。

$\texttt{ 03.in, 03.out }$

数据满足 $n=21,m=50$ ，随便写个爆搜即可。

参考代码

$\texttt{ 04.in, 04.out }$

数据满足 $k=2$ ，是张二分图，直接黑白染色。

参考代码

$\texttt{ 05.in, 05.out }$

数据满足 $k=3$ ，观察发现在 $\% 10$ 意义下， $\{0, 1, 2\}, \{ 3, 4, 5, 6\}, \{ 7, 8, 9\}$ 合法。

参考代码

$\texttt{ 06 - 11 , 18 }$

按照 $deg$ 从大到小排序，然后加入少量扰动，暴力 $check$ 即可。跑起来飞一样快。

参考代码

$\texttt{ 12.in, 12.out}$

观察发现按照 数位和$\% 4$ 进行分组满足条件。

参考代码

$\texttt{ 13.in, 13.out }$

观察发现按照 数位和 $^2 \%4$ 进行分组满足条件。

参考代码

$\texttt{ 14.in, 14.out }$

注意到 $k=10,n=2000$，显然是对于 $popcount(x)$ 的值进行分组。

参考代码

$\texttt{ 15.in, 15.out }$

注意到 $k=6$ ，而 $max\{ \omega (n)\} (1\le n\le 10^5) = 6$ ，因此联想到将 $i$ 放置在 $\omega (i)$ 组里。

参考代码

$\texttt{ 16.in, 16.out }$

按照 $d(i) \% 13$ 放置即可。

参考代码

另外，将我的代码改成扰动 $50$ 个点对，竟然碾过去了。。。

参考代码

$\texttt{ 17.in, 17.out }$

试了好久……按照 $n=p_1^{a_1}...p_k^{a_k}$ ，记 $f(n)=\sum\limits_{i=1}^{k} a_i \% 13$ ，则 $i$ 属于 $f(i)$ 组。

参考代码