高度由习惯堆积

分类 数据结构:点分治 下的文章

NOI2014 购票

各位dalao的解法都好神啊。。。这里给一种点分治的解法。题目链接思路首先斜率部分。转移方程:$ans[x]=min(-dis[u]*p[x]+ans[u])+dis[x]*p[x]+q[x]$发现结果只与$min()$框内的部分有关,观察这个形式,发现是个一次函数,也就是说可以斜率优化。dalao们对于推斜率式子这部分表示很不屑,但是我太菜了,所以还是写一下吧。令$p=p[x]$,当$u$...
February 15, 2019

POJ1741 Tree(点分治)

题目给一棵边带权树,问两点之间<=K的点对有多少个。思路题目很简单,但是思路很经典。首先确定点分治的基本框架,假设一定要经过一个根。下面还要用到容斥的思维。对于一个根,我们没法直接统计路径长度不超过k的路径条数,那需要一点技巧。处理出子树中所有的dis值放入B数组中,再对于当前A子树,加上其对于B所做的贡献,减去其对自身所做的贡献,就是它对其他子树所做的贡献。看似简单,其实在点分治问题...
February 9, 2019

HDU4871 Shortest-path tree(点分治)

题目题面大意是给你一个图,要你构建出一棵最短路树,再询问经过k个点的最长路径长度以及最长路径条数。思路点分治。点分治的思路是这样的:对于一个点$x$而言,对答案有影响的路径要么经过点$x$要么不经过,利用这点进行分治。点分治首先要找出一个重心。重心是指以该点为根所有的子树中sz最大的最小。然后,对于每一棵子树进行处理,统计答案(点分治题目不同的地方就在这,其它都是板子)之后再递归进重心的子树...