CF1738F Connectivity Addicts

给定 \(n\) 个点的度数，你需要在 \(n\) 次询问内给出一种涂色方案，使得每个颜色都满足 \(s_c\leq n_c^2\) ，其中 \(s_c\) 表示所有点的度数和， \(n_c\) 表示点的个数。每次询问给出一个点，交互库将会回答你任意一个和这个点相连的点，若多次询问同一个点，则保证给出的点不相同。多组询问， \(\sum n\leq 1000\) 。

这题放了 \(O(n^2)\) 的做法？

首先是一个乱搞（然而这一题好像乱搞很难做出什么名堂来），什么怼着 \(deg\) 最大/小的点死问是肯定错误的，但凡有意将回答的顺序设为老是先回答那几个就寄了。

然后考虑正解，这里给出一个正确的做法，正确性是口胡的。

首先将度数从大到小排序，并给每个点附上一个单独的颜色。顺次取出每一个点，若点所在颜色集合满足 \(s_c\leq n_c^2\) 就跳过，否则就询问这个点，然后将 \(2\) 个颜色进行合并，直到这个点被问完或者这个点所在颜色满足条件，这个过程可以用并查集维护。

感觉这个做法和官方题解差不多，但是官方做法比较好证明查询次数小于等于 \(n\) 。

放个链接，这个坑待填。 Editorial of Codeforces Global Round 22 – Codeforces

感觉这个做法和乱搞没太大区别啊

原文地址：http://www.cnblogs.com/zhouzizhe/p/16825533.html