RainAir
My OI Blog
RainAir

RainAir’s Blog

  SDOI 2019 Bless All!

密码保护:疯狂!大礼堂变教室,百名中学生初八进鲁参加竞赛培训,自主招生成新噱头

这篇文章受密码保护,输入密码才能看哦

   328   2019-02-16 去围观

二维树状数组学习笔记

我们把树状数组由一维扩展到二维。二维树状数组的定义是: $C[x][y] = \sum A[i][j]$,其中 $x - lowbit(x) + 1 \leq i \leq x$ $y - lowbit(y) + 1 \leq j \leq y$ 所以我们就可以很方便的写出来单点修改和查询 $(1,1)$ 到 $(x,y)$ 的和的代码了: [crayon-5c7122dd…

   105   2019-02-07 去围观

「BZOJ5415」「NOI2018」归程

题目链接 题解 首先我们尝试把不能被车经过的边删掉,得到了一张新图。这个新图上每一个连通块的答案都相同。 所以 Dijkstra 是首先要跑的。然后我们发现如果可以离线的话我们可以把边和询问放在一起排序,用普通的并查集维护一下每个连通块到 $1$ 节点的最短距离就…

   87   2019-02-07 去围观

Splay 如何维护区间信息

如何维护区间 我们都知道平衡树是一种很神奇的东西,可以用于维护动态的序列总信息,但是如果想维护其中的某一个区间的信息,我们该怎么做好呢? 我们考虑换一种维护方式:平衡树的结构不是按照节点的值的大小来进行建树,而是以这个节点在序列中的位置为关键字来维护…

   97   2019-02-02 去围观

「BZOJ4906」「BJOI2017」喷式水战改

题目链接 题目大意是对于每种物品被划分到不同的组里会产生不同的贡献,求一种最大的划分(这里的划分是连续一段划分到一起),并且要动态维护这个东西。 我们首先考虑静态如何做这个东西,显然我们可以设出一个极为暴力的状态:$f(l,r,i,j)$ 表示燃料 $[l,r]$ 使用…

   99   2019-02-01 去围观

KD-Tree 学习笔记

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

   112   2019-01-31 去围观

LCT 维护子树信息

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

   71   2019-01-30 去围观

「BZOJ2002」「HNOI2010」弹飞绵羊

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

   85   2019-01-29 去围观

点分治初探

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

   82   2019-01-29 去围观

树上启发式合并学习笔记

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

   80   2019-01-29 去围观
加载更多
文章归档