louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共3篇）

题解 | 算法竞赛进阶指南清理班次

思路先将所有左边界-1,也就是将所有"块"变成"点",从"第l块到第r块"到"坐标之间的块",方便离散化.先对所有区间按右边界排序,枚举每个区间,更新答案大家可能发现我的转移方程与算法竞赛进阶指南上不太一样,因为我的表示方式不同,书上表示覆盖第1块到第i块都被覆盖过的最优答案,而我是坐标从到之间所...

线段树动态规划

2019-08-25

0 570

题解 | 算法竞赛进阶指南雨天的尾巴

思路好恶心的卡常题(虽然一边颓废一边写,还是卡了一下午).如果空间和时间足够大,我们可以考虑对每一种粮食开一个大小的数组,若某条路径放类型的粮食,,树上前缀和,然后找出最大值即可.不过这样就算是离散化后,时空复杂度都是.不过这样直接把开的数组改成动态开点线段树就好了.求前缀和的过程可以看成线段树合...

线段树前缀和树上倍增

2019-08-22

0 618

题解 | 算法竞赛进阶指南 Atlantis

(话说这篇题解我在洛谷发过,所以图有水印...) 思路扫描线经典题.图1我们从左到右扫描所有的纵向边. 图2 - 红色边即为依次扫描到的边. 这些边可以用一个结构体记录.需要记录横坐标,上下边界(纵坐标),是一个矩形的结束还是开始.扫描这些边时,我们用数据结构维护每个位置纵坐标被矩形覆盖了多少.如...

线段树扫描线离散化

2019-08-20

0 789