UVALive 5848. Soju

题目大意

给定两个平面上的点集,求两个点集中距离最近的两个点的距离。(这里的距离说的是曼哈顿距离。)题目中保证了左边点集的点都一定在右侧的点集的左侧。也就是任意一个在左侧集合的点的横坐标都小于任意一个在右侧集合的点。

分析

题目中反复的提示了左侧的点一定在左侧。那么来分析曼哈顿距离的式子:

其中令(x_1, y_1)是处于左侧的点的话,其中的第一项一定是小于0的,可以去掉绝对值符号。那么我们如果令我们枚举的右侧点在左侧点的下面的话,右侧的绝对值就也可以去掉了。那么式子就可以变成如下的形式:

[(y_1-x_1)-(y_2-x_2)]那么这个时候只要维护后一项的值最大就好了。对于......

president-tree-learning

主席树我的理解是可持久化线段树的一种应用吧。本质上就是可持久化线段树,不过我们在查询的时候用到了他们之间可以相减的性质。

首先介绍一下可持久化线段树。

可持久化线段树

可持久化线段树是可持久化数据结构中的一种,主席树的实现就是利用了可持久化线段树的。

可持久化数据结构

所谓的可持久化数据结构,就是保存这个数据结构的历史版本,同时应该公用他们的公有部分来减少内存上的消耗。

可持久化线段树

在每次更新的时候,我们保存下来每次更新的历史版本,以便我们之后查阅。在主席树中我们用到的线段树是保存当前范围内位置有多少个数的。以下都用这个当例子。

下面图中点的表示:

建树

建立一颗空树......

2015多校Contest 5. 1003. Hotaru's problem

题目大意

一个N-sequence由三个部分组成,并符合:

第一部分和第三部分相同。

第一部分和第二部分回文。

求最长的N-sequence的长度。

分析

N-sequence的特征是第一部分和第三部分相同,并且第一部分和第二部分回文。那么条件可以转化成:第一部分和第二部分 回文,并且第二部分和第三部分 回文。那么问题就转化成了:两个回文串的重合问题。

先用manacher求出任意一个位置作中心的最长回文串的长度。因为第一部分和第二部分组成的回文串s1一定是一个偶数长度的串,所以一定是我们添加的#位置。每个中间位置i可以覆盖左边的i-rad[i]到右边的i+rad[i]的范围......