XLor

题解

/ 注册

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

G. Greetings Souvenir 题解

问题是要求，考虑二分答案后，使用二分图匹配判断是否流满。但是，我们不能暴力的去建出二分图，对建图进行优化。首先，我们考虑对每种颜色建出虚树，那么一条边就对应原树的一条垂直树链，这条链上任取一个点都会产生颜色树乘子树关键点数的值，因此需要将这条路径的所有点连向某个值。然后，这里给一个个点，...

线段树树链剖分网络流

2020-07-26

4 1207

K. Keyboard Free 题解

固定点，枚举点，计算点到直线的期望高度。如上图，为第一个动点，为第二个点，通过可以算出线段的长度，进而得到 ()。此时，可以丢弃这个斜着的图形，只保留该角度放正图形容易进行积分，得到期望高度为。由于做了两次积分，两个随机变量都服从的均匀分布，需要除两次。 ...

概率期望积分几何

2020-07-14

6 806

2019牛客多校第 1 场 I 题题解

题目描述给定个二维平面上的点，每个点有权值和。将点集划分为两个集合，满足任意 A 集合的点和 B 集合点，要么，要么。 A 集合的点使用权值，B 集合的点使用权值，求最大化权值和。分析题目即是用一个阶梯型的分段函数将点集划分为两块，A 集合在左上，B 集合在右下，边界...

线段树扫描线动态规划

2019-07-19

0 1141