首页 > [JSOI2008]星球大战STARWAR
开通博客写题解
头像 sunny_forever
发表于 2021-08-07 21:19:01
并查集 + 邻接表 + 逆向思维 逆向思维: 原题意：共要删除 k 个点，问：每次删除过后，连通块个数是多少？ 逆向思维：删点 ==> 加点、连边 对！没错，变成了加点与连边 所以最开始，我们只对 n-k 个点进行合并操作就行，然后枚举每个要删除的点（注意是从后向前枚举） 对于每个枚举到 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 yizimi远欣
发表于 2018-12-02 23:25:00
主要思路：逆向思维 看到题目，第一个感觉，，， 连通块？？？ 我刚学过的搜索呢？？？深搜广搜都可以啊QwQ！ 但很多人都被困在了这个攻占星球（也就是去点）上。 如果再仔细看下题目，发现可以离线做这道题。 那么方法来了： 我们是不是可以把所有的边存下来，把被攻 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”