TitanZhang

分类

算法浅谈(1) 题解(48)

/ 注册

TA的专栏 47篇文章 1人订阅

2020牛客暑期多校训练营

47篇文章 1255人学习

全部文章（共1篇）

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

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

期望线段树

2020-08-09

2 804