线段树模板

线段树模板,支持对区间做运算并求sum,基于POJ 3468
需要注意:

  • 数组开4倍大

  • 因为区间操作较频繁故打标记

  • 注意Update操作的位置

  • 均为1~n,所以包括左右,分段递归注意端点要被包含


阅读剩余部分 -

配置instantclick支持prism高亮与mathjax

由于instantclick实现的是PJAX,headfooter之间的内容并不会更新,而这一部分我加载了渲染代码高亮的prism.jsMathjax以及谷歌的analytics.js,所以貌似除了Google其他的js都不会正常加载,根据instantclick官网的说明,只需要改动一下绑定的事件即可,加载instantclick的部分修改为如下

阅读剩余部分 -

后缀数组

最长公共子串问题(LCS)

  • 定义:给定字符串长度最大的公有子串,使用后缀数组可达到$O(nLlogL)$,其中$n为字符串个数$,$L$为每个字符串长度

  • 等效于求两个后缀的公共前缀(LCP)

后缀数组相关概念

  • SA[i]:排名为i的后缀的位置(第i是谁)

  • Rank[i]:第i个后缀suffix(i)的排名

  • 对于已经排好序的字符串,任意两个的公共最长前缀为$LCP(s[i], s[j]) = min \{ LCP(s[k], s[k + 1]) , i \le k < j\}$,LCP转化成区间最小值RMQ问题

  • height[i]:定义height[i] = LCP(SA[i - 1], SA[i]),则$LCP(s[i], s[j]) = min \{ height[k] , i \le k < j\}$

阅读剩余部分 -

图与基本的图算法

图的基本概念及表示

图的基本概念

逻辑结构二元组B=(K,R),任意一对结点间都允许一个关系存在

  • 分类:无向图、有向图、带权图、稠密图、完全图、连通图等

  • 最一般的数据结构

表示:G=(V, E),有向完全图 $n (n - 1)$ 条边,无向完全图 $n (n - 1) / 2$ 条边

带权的连通图称为网络

图G有$n$个顶点,$e$条边,顶点$v_{i}$的度数为$TD(v_{i})$,则有$$e = \frac{1}{2} \sum_{i = 0}^{n - 1}TD(v_{i})$$

环:回路,无向图平行边不构成环,有向图两条边可构成环

阅读剩余部分 -

最新文章

最近回复

分类

归档

其它

微博

基佬们

Fork me on GitHub