首页 > 数树
开通博客写题解
头像 Deep_Dark_FAntasy♂
发表于 2020-09-26 10:58:27
思路：可以从度的角度来考虑来考虑相连如果是两个D>1的结点相连，我们知道这一定是两颗树合并了，那么树++，如果其中一个D=1，那就是一个点和并到了一颗树上，树的个数不变，如果两个D=0的点相连，树的个数++接下来考虑断开如果是两个D>1的结点断开，我们知道肯定是1棵树变成了2颗树。如果其 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 范艺杰
发表于 2020-09-27 09:13:27
没看到题目中条件保证是一颗森林，自行加强题目。这里采用时间线段树+回退并查集来解决。并查集可以O(1)的插入，很难O(1)的支持删除操作，但是可以回退。我们使用时间线段树，将所有操作锁定为插入操作，使用回退并查集维护即可。复杂度O(nlogn)。 #include <cstdio> #i 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 小涂同学啦啦啦
发表于 2020-09-25 22:46:59
这个题其实还是比较简单的，有一点点图论基础都能做。题目的意思n次操作，操作1给a,b加边（重边直接忽略）。操作2给a,b删边（不存在则忽略）。操作3 输出当前不为1的树的数量。题目数据非常amazing啊，直接把点拉到了1e8，出题人甚至专门写了一句话要玩家注意范围。对此，我们离散一下就好了。轻松破 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 sunsetcolors
发表于 2020-09-25 23:41:12
D 数树 题目地址： https://ac.nowcoder.com/acm/contest/7509/D 基本思路： 我们发现既要加边又要删边,显然不好用并查集维护,那么我们关注要求的答案只是有多少个大小不为一的树,因为没有环,其实也就是有几个大小不为一的连通块,那么一个联通块大小为一,就 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 回归梦想
发表于 2020-09-26 15:00:57
来源：牛客网： 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 小牛牛在暑假的时候返乡务农。为了响应习主席“绿水青山就是金山银山”的号召开始种树。 但他种树的方式比较奇怪。他会先拿出一些有 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”