DP总结 发表于 08-21-2019 本文字数: 3.4k 阅读时长 ≈ 3 分钟 背包 $\mathbf{DP}$$DP$ 的背包问题是最基础的 $DP$ 了,分为 $01$ 背包,完全背包和多重背包。 $\mathbf{01}$ 背包$01$ 背包基本模型,背包的总体积为 $V$ ,总共有 $n$件物体,每件物品的体积为 $v_i$ ,价值为 $w_i$,每件物品只有一个,选择 ... 阅读全文 »
数据结构总结 发表于 08-21-2019 本文字数: 6.6k 阅读时长 ≈ 6 分钟 基础数据结构基础数据结构包括数组,链表,栈,队列等,过于基础,再次不在赘述。 并查集普通并查集并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。首先把每个点指向的父亲结点初始化为自己,然后根据要求进行查找和合并。合并的时间复杂度是$\Theta(1)$ 的 ... 阅读全文 »
图论总结 发表于 08-21-2019 本文字数: 6.3k 阅读时长 ≈ 6 分钟 最短路算法$\mathbf{Floyd}$ 算法思路简介$Floyd$ 算法的思想本质是一个 $DP$ ,首先枚举中间点 $k$ ,对于每条路径$i->j$ ,判断此路径若经过点 $k$是否更优。状态转移方程为 $dis[i][j]=\min(dis[i][k]+dis[k][j],dis[i ... 阅读全文 »
数论总结 发表于 08-21-2019 本文字数: 5k 阅读时长 ≈ 5 分钟 基础数论扩展欧几里得算法 $\mathbf{exgcd}$首先介绍一下贝祖定理。若 $a,b$ 是整数,那么 $a\cdot x+b\cdot y=\gcd(a,b)$一定有解。如果需要判断 $a\cdot x+b\cdot y=c$ 有没有解,可以直接判断 $c|\gcd(a,b)$可以用欧几里得 ... 阅读全文 »
浅谈KMP 发表于 07-14-2019 更新于 08-22-2019 本文字数: 2.3k 阅读时长 ≈ 2 分钟 什么是 $\mathbf{KMP}$$KMP$ 算法是一种改进的字符串匹配算法,由$D.E.$ K $nuth$,$J.H.$ M $orris$和$V.R.$ P $ratt$提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称 $KMP$ 算法)。 $KMP$ 算法的关键是利用匹配失败后的信息 ... 阅读全文 »
浅谈Splay 发表于 07-10-2019 更新于 08-22-2019 本文字数: 8.2k 阅读时长 ≈ 7 分钟 什么是 $\mathbf{Splay}$伸展树($Splay\quad Tree$),也叫分裂树,是一种二叉排序树,它能在 $\Theta(log_2 n)$ 内完成插入、查找和删除操作。它由丹尼尔·斯立特( $Daniel\quad Sleator$ ) 和 罗伯特·恩卓·塔扬( $Robert\ ... 阅读全文 »