TitanZhang

题解

算法浅谈(1)

/ 注册

全部文章 / 题解（共2篇）

2020牛客暑期多校训练营（第九场）C-Groundhog and Gaming Time 来自专栏

题目大意给定n个区间[L_i, R_i]，每个区间有 1/2 的概率被选择，表示第i个被选择的线段，求的期望，答案对998244353取模。解题思路不同于官方题解通过树形dp的思路，我们的方法是通过累加每种情况对期望的贡献来求解。线段的交取决于最大的左端点以及最小的右端点，同时维护两个东西比...

期望线段树

2020-08-09

2 804

2020牛客暑期多校训练营（第四场）A Ancient Distance 来自专栏

题目大意给定N个点构成的有根树，顶点编号从1-N，根节点为1号点。你可以选最多K个点（根必须选），使得所有点的最大“祖先距离”尽可能的小。点x的“祖先距离”是在点x到根节点上的路径上，点x与第一个关键点的距离。若没有关键点，则距离为正无穷大。（例如1-2-3树上，关键点为2，则三个点...

线段树 DFS序

2020-07-23

1 741