uniHk

分类

01Trie(5) AC自动机(7) CDQ分治(4) dsu on tree(1) K-D Tree(5) 主席树(5) 各类说明(1) 后缀数组(1) 后缀自动机(11) 回文自动机(6) 字符串（杂）(6) 康托展开(1) 数学(7) 整体二分(1) 斜率优化DP(3) 树链剖分(3) 概率DP(2) 算法(Lazy)(38) 线性基(5) 莫队(6) 计算几何(3)

/ 注册

全部文章（共121篇）

喵星球上的点名（后缀自动机+dfs序+莫队）

喵星球上的点名一道据传言有多种解法的题（不过大多是因为数据太弱过的）。先用AC自动机搞了一上午，无果；看了题解，后缀自动机+莫队？正好是我最喜欢的算法之一+正在学习的算法，就这个了！然后由于广义自动机的 l ...

2020-01-02

0 459

大爷的字符串题（莫队）

大爷的字符串题莫队板子题。。。因为离散化的 n n nn ...

2020-01-02

0 494

小清新人渣的本愿（莫队+bitset）

小清新人渣的本愿这两天写了些 b i t s ...

2020-01-02

0 398

The Kouga Ninja Scrolls（2018沈阳现场E+切比雪夫距离+线段树维护最大次大最小次小）

The Kouga Ninja Scrolls 这题可真暴力呀！曼哈顿距离转成切比雪夫距离后大力线段树搞即可！第一次把线段树封装一下，为了 x , ...

2020-01-02

0 563

最短不公共子串（后缀自动机+序列自动机+bfs）

最短不公共子串题意：问最短的满足：是A的子串（子序列），且不是B的子串（子序列，子序列（子串））。（共四个问题）思路：子串问题，考虑后缀自动机；子序列问题，考虑序列自动机；这不就成板子题了？然后本题要求属于前者，而不属于后者的子结构，可以考虑暴力的在两种DAG上同时跑；若...

2020-01-02

0 461

简单题（K-D Tree+单点插入+矩形区间和）

简单题不知道为什么取这个名字QAQ，有个地方初始化不对，在洛谷上挂了一页。题意：特点：强制在线(last_ans)+20M内存限制思路：没啥思路，就是K-D Tree板子题，因此下面记录K-D Tree的一些信息 K-D Tree也算二叉+平衡+树吧？用于维护K-Dimen...

2020-01-02

0 419

K远点对（K-D Tree）

K远点对 K-D Tree 真是优雅的暴力！开局建棵树，剪枝刷题数！题意：给定二维平面上的 N N N个点，求第 ...

2020-01-02

0 748

Finding Hotels（2017ICPC青岛现场K题+K-D Tree）

Finding Hotels 在前车之鉴的基础上，真好，又是 1 A 1A ...

2020-01-02

0 485

TATT（K-D Tree + 四维偏序）

TATT 题意：求最长的非递减的四维偏序长度。思路：先将序列任选一个维度进行排序，然后依次将这些点插入到K-D Tree中。每插入一个点之前，计算以当前点结尾的最长偏序长度（剩下的是三维偏序问题），然后再将当前点插入即可。当然，K-D Tree重点还是在剪枝上。此处考...

2020-01-02

0 440

JZPFAR（K-D Tree + 第K远点）

JZPFAR 题意：给定平面上 N N N个点，然后 M ...

2020-01-02

0 396