XLor

分类

题解(3)

/ 注册

全部文章（共2篇）

G. Greetings Souvenir 题解

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

线段树树链剖分网络流

2020-07-26

4 1207

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

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

线段树扫描线动态规划

2019-07-19

0 1141