• 欢迎光临~

CF1738F Connectivity Addicts

开发技术 开发技术 2022-10-25 次浏览

CF1738F Connectivity Addicts

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

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

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

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

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

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

放个链接,这个坑待填。 Editorial of Codeforces Global Round 22 - Codeforces

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

程序员灯塔
转载请注明原文链接:CF1738F Connectivity Addicts
喜欢 (0)