RainAir
My OI Blog
RainAir


文章归档

KD-Tree 学习笔记

K-D Tree,全名k-dimensional Tree,是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。K-D Tree是二进制空间分割树的特殊的情况,以下是一棵二维空间上的 k-d tree: 建树 K-D Tree 的建树过程类似于平衡树:对于…

   332   2019-01-31 去围观

LCT 维护子树信息

众所周知 LCT 可以用来维护动态树的点权信息,但是总有一些题目让你维护动态树上的子树信息或者是链信息,就在这里拿一道经典的题目讲一讲。 「UOJ207」共价大爷游长沙 题目链接 题目要求维护动态树和一个路径集合,询问某一条边是否被路径集合中所有的路径经过。 首…

   273   2019-01-30 去围观

「BZOJ2002」「HNOI2010」弹飞绵羊

题目描述 题目链接 某天,Lostmonkey 发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置,每个装置设定初始弹力系数 $k_i$,当绵羊达到第 $i$ 个装置时,它会往后弹 $k_i$ …

   245   2019-01-29 去围观

点分治初探

点分治是什么: 首先选取一个点将无根树转为有根树,再递归处理每一棵以根节点的儿子为根的子树。 这样得到的分治结构有何用处? 通俗地讲,对任一个点,树的任一条路径要么经过这个点,要么不经过这个点,在这个点的子树里面。这对于树路径的计数等问题能够更容易的解…

   224   2019-01-29 去围观

树上启发式合并学习笔记

首先什么是启发式算法?启发式算法是基于人类的经验和直观感觉,对一些算法的优化。 最简单的就是并查集的按秩合并,每次把小的合并到大的上面,这样找父亲的复杂度就小了很多。 树上启发式合并(dsu on tree)是一种我也不知道为什么叫做这个名字的奇怪算法。 特点是…

   230   2019-01-29 去围观

「CF487E」Tourists

题目链接 题目描述 给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作,要么修改一个点的点权,要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径,路径上最小点权最小值是多少。 $ n,m,q \leq 10^5 $. 题解 问的是所有可能路径上的最小点权的最小值,那我们…

   274   2019-01-23 去围观

点双连通分量 & 圆方树学习笔记

点双连通分量 点双连通图:如果一个无向图上没有割点,那么该图为点双连通图。显然有一个性质是同一个点双连通图中任意两点至少存在两条不经过重复点的路径。 点双连通分量:一个无向图的极大点双连通子图 我们可以使用 Tarjan 求解。 大家肯定都会无向图求割点了,我…

   527   2019-01-21 去围观

最小树形图 / 朱刘算法

前置定义 树形图:在一个有向图中,满足存在一个入度为 $0$ 的点,除了该点入读均为 $1$,且该图不存在环,那么称为树形图。 最小树形图:给定有向边权图,求以某点为根的边权和最小的子图,满足该子图为树形图。 朱刘算法 模板链接 相当于是一种贪心的思想。 首先…

   186   2019-01-20 去围观

「数学基础」莫比乌斯反演

UPD:狄利克雷卷积的单位元表示符号建议使用 $\epsilon$。 积性函数 定义 对于一个函数 $f$,若有 $\forall x,y,(x,y)=1,f(xy) = f(x)*f(y)$,则我们称这样的函数为积性函数。 举例:$\phi(x),\mu(i),d_k(n)$($n$ 的所有正因子 $k$ 次幂和) 性质 若 $f(x)$ 为积…

   286   2019-01-14 去围观

「BZOJ 3669」「NOI2014」魔法森林

题目链接 题目简述 给定 $N$ 个点 $M$ 条边的无向图,每条边有两个权值 $a$ 与 $b$ 。求一条 $1$ 到 $n$ 的路径使得路径经过边的最大 $a$ 与最大 $b$ 的和最小。无法到达输出 $-1$。 $ n \leq 50000,m \leq 100000$。 解题报告 乱入:这个题目只需要枚举 a 然后动…

   319   2019-01-06 去围观
加载更多
文章归档