并查集——并查集的优化
查询优化 路径压缩 很显然，我对我的爸爸或者爷爷是谁并不在乎，我只在乎我的祖先是谁。 根据这样的思路，路径压缩的并查集就诞生了 int find(int x) { if (x != fa[x]) // x不是自身的父亲，即x不是该...
查询优化 路径压缩 很显然，我对我的爸爸或者爷爷是谁并不在乎，我只在乎我的祖先是谁。 根据这样的思路，路径压缩的并查集就诞生了 int find(int x) { if (x != fa[x]) // x不是自身的父亲，即x不是该...
对于并查集的定义其实并不难理解 通俗的理解可以是：你是我的亲戚，他是我的亲戚，那你和他同样也是亲戚。通过合并而查索之的操作，可以实现在较小的时间复杂度下完成对一些不交集的 合并 及 查询 问题 ...
本文所有的证明均参见OI Wiki 欧几里德定理 证明参见OI Wiki $$gcd(a,b)=gcd(b,a \; mod \; b)$$ 利用这一重要的定理，容易发现这样的操作递归到最后一定会得到一个\(gcd(m,0)\)，此时值为m，我们就可以利用递归法...
链表链表，顾名思义，指的是由链子组成的数据表。 与我们常见的数组，栈，队列等顺序数据结构不同，链表的存储是不连续的。这时候可能有聪明的小朋友就要问了：“不连续存放数据怎么对数据操作啊？”别忘了，我们有链子啊。打个比方...
——以“最长回文子串”及“回文子串个数”为例 首先明确，这两题使用动态规划均能求解，不过复杂度还是相对较高 这里先给出动态规划的状态转移方程，有兴趣的读者不妨一试 \(dp[i][j]\)表示字符串中从\(i\)到\(j\)的子串是否为回...
——以“钻石收集者”与“Subsequence”为例 如果有同学细心去做Codeforces，会发现有这么一类标签叫Two Pointers。没错，这就是我们今天的主角——尺取法。 还有一部分同学会将尺取法叫成毛毛虫法。 其实这是相当形象的一种叫法，...
set是STL的一个关联容器并带有自动排序和去重的功能 Sets are containers that store unique elements following a specific order. ——C++ Reference set的操作并不复杂，有以下几种 迭代器begin cbegin 返回指向...
以“【模板】单源最短路径（弱化版）”为例 最短路径是图论当中的重点内容之一 这里我们借由洛谷上的一条模板题来理解一下什么是SPFA 首先明确，SPFA并不是一个算法的名字，这只是一个中国老师在1996年在Bellman–Ford算法基础...
本篇将介绍在各类算法竞赛中应用广泛，也是最为基础的一种素数筛法，欧拉筛，他的本质是Eratosthenes筛的优化 在介绍欧拉筛之前，我们不妨先整体感悟一点就是素数的存在虽然是无序 的 （至少目前并没有有力的证明素数的分布存在一...
map是STL的一个关联容器。 它提供一对一（其中第一个可称为关键字（Key），每个关键字只能在map中出现一次，第二个可称为该关键字的值（key_Value））的数据处理能力。 map的用法为 map< class _Key, class _Tp> 元素访...