首页 > Cover the Tree
开通博客写题解
头像 TitanZhang
发表于 2020-07-14 14:29:00
题目大意 给定一棵无根树，连接其中两个节点组成一条链，使树中的每一条边至少被一条链覆盖。 输出最少的链数量+其中任何一个解决方案。 解题思路 先引用原题的一个（水）测试样例： 5 <--节点数量 1 2 <--节点中连的边（节点数量-1条） 1 3 2 4 2 5 可以 展开全文
去ta的博客 赞 (3) 回复(2) 收起
头像 TitanZhang
发表于 2020-07-14 15:32:53
题目大意 给定整数n,m,k，构造一个n×m的矩阵A，其中Ai,j = lcm(i,j)，第i行j列的数是i和j的最小公倍数。 求所有k×k个子矩阵中的最大值之和。 解题思路 先用尽可能快的操作将整张表求出来，接下来用单调队列。（附上大佬详解链接https://www.c 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 mutou01
发表于 2020-07-21 10:23:42
2020暑期D2-C 思路+证明主为自用，欢迎指正。 https://ac.nowcoder.com/acm/contest/5667/C 前置知识：树中链的覆盖，节点A到节点B的经过尽可能少的点的路径（最短路径），亦可以理解成一种遍历经过的路径，经过的点和边都是覆盖。dfs序，树在dfs遍历时，树 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 cheeserish
发表于 2020-07-14 23:21:45
标程写法：n<=2时，显然==s/2（s为叶子结点数） s>=3时，将结点按照dfs序排序，l1,l2,l3...假设s为偶数； 那么对于l1->ls/2+1, l2-> ls/2+2... 假设这条链上的儿子结点所覆盖的区间【l，r】, 如果 r < = s/2 ,那 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 zjnu_tjq
发表于 2020-07-17 21:06:44
链接：https://ac.nowcoder.com/acm/contest/5667/C来源：牛客网 题目描述: Given an unrooted tree, you should choose the minimum number of chains that all edges in the 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 回归梦想
发表于 2020-07-24 16:53:51
Cover the Tree@[toc] 题意： 一个无向树，选择最少数量的链子，能将树上所有边覆盖，答案不唯一(1≤n≤2×10^5^）链子就是两点之间的边看看样例输入 5 1 2 1 3 2 4 2 5 输出 2 2 3 4 5 一种情况如图所示：所有边被覆盖的链子有：链子2->3:覆盖了 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”