zhanGTao_

分类

未归档(1) 题解(4)

/ 注册

全部文章（共2篇）

题解 | #数轴覆盖#

前缀和做法使用一个 dpdpdp 数组记录前缀和，dpidp_idpi 表示在 [0,i][0,i][0,i] 中有多少个点。枚举起点 iii 即可得到线段终点 i+k−1i+k-1i+k−1 , 使用 dpi+k−1−dpi−1dp_{i+k-1}-dp_{i-1}dpi+k−1−dpi−...

C++ 前缀和双指针动态规划

2021-10-20

0 443

题解 | #小红的树#

非树形DP做法知识点：DFS序维护子树信息，前缀和由于DFS过程是遍历当前节点的全部子节点后返回当前节点，所以利用这个性质可以有效维护子树信息。 DFS过程中使用一个时间戳 dfndfndfn 并记录进入某个节点的时间 ininin 和出这个节点的时间 outoutout 。我们记录一个DFS序...

C++ 深度优先搜索前缀和

2021-10-19

0 549