• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

NOIP 前做题

开发技术 开发技术 3小时前 2次浏览

CF1439B Graph Subset Problem

对于二可以用一个经典的求 k-core 的算法,每次拓扑删除那些度数小的点。然后到了 (k) 的时候我们就直接看一下是不是全部被删光了即可。

关于第一个求团。我们发现一个大小为 (k) 的团在不存在 k-core 的情况,这些点都必然是 (k-1)-core 中的点。于是我们对于每个在求 (k-1) 的时候求出来的点遍历它所有连接的点,然后判断是否是团。这个单次操作是 (O(k^2)) 的。

但是,实际上 k-core 点的个数是 (O(m/k)) 的级别的,这意味着求团的复杂度为 (O(mk))。然后,团的边数应该在 (O(k^2)=O(m)),也就是说复杂度是 (O(msqrt{m}))

具体操作时,我们维护一下 deg,然后用 unordered_map 作邻接矩阵。本人曾经使用过 unordered_set 来代替 vector 和 deg 存邻接表,然后被卡常死了。然后数据中还存在卡 unordered_map 的数据……

https://codeforces.com/contest/1439/submission/131558660

CF1340D Nastya and Time Machine

考虑其欧拉环游序。每一次一个点出现,它必然是不同的时间。可以得到理论下界为 (D=max deg(u))。实际上这个下界可以达到。考虑钦定每个点出来的时间是进来的时间 -1。这是可以构造完成的。遍历的时候,如果一个点加到 (D),就穿越到 (D-deg(u))

https://codeforces.com/contest/1340/submission/131561302

CERC2014 Outer space invaders


程序员灯塔
转载请注明原文链接:NOIP 前做题
喜欢 (0)