题解 P6865 【[RC-03] 染色】
wlzhouzhuan
·
·
题解
洛谷 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) 组。
参考代码