倚栏听风——小白开发日志

倚栏听风——小白开发日志

查询优化 路径压缩 很显然,我对我的爸爸或者爷爷是谁并不在乎,我只在乎我的祖先是谁。 根据这样的思路,路径压缩的并查集就诞生了 int find(int x) { if (x != fa[x]) // x不是自身的父亲,即x不是该...

发布 1条评论 2631次浏览

对于并查集的定义其实并不难理解 通俗的理解可以是:你是我的亲戚,他是我的亲戚,那你和他同样也是亲戚。通过合并而查索之的操作,可以实现在较小的时间复杂度下完成对一些不交集的 合并 及 查询 问题 ...

发布 0条评论 2587次浏览

本文所有的证明均参见OI Wiki 欧几里德定理 证明参见OI Wiki $$gcd(a,b)=gcd(b,a \; mod \; b)$$ 利用这一重要的定理,容易发现这样的操作递归到最后一定会得到一个\(gcd(m,0)\),此时值为m,我们就可以利用递归法...

发布 0条评论 1710次浏览

链表链表,顾名思义,指的是由链子组成的数据表。 与我们常见的数组,栈,队列等顺序数据结构不同,链表的存储是不连续的。这时候可能有聪明的小朋友就要问了:“不连续存放数据怎么对数据操作啊?”别忘了,我们有链子啊。打个比方...

发布 0条评论 2066次浏览

——以“最长回文子串”及“回文子串个数”为例 首先明确,这两题使用动态规划均能求解,不过复杂度还是相对较高 这里先给出动态规划的状态转移方程,有兴趣的读者不妨一试 \(dp[i][j]\)表示字符串中从\(i\)到\(j\)的子串是否为回...

发布 2条评论 1827次浏览

——以“钻石收集者”与“Subsequence”为例 如果有同学细心去做Codeforces,会发现有这么一类标签叫Two Pointers。没错,这就是我们今天的主角——尺取法。 还有一部分同学会将尺取法叫成毛毛虫法。 其实这是相当形象的一种叫法,...

发布 3条评论 2046次浏览

set是STL的一个关联容器并带有自动排序和去重的功能 Sets are containers that store unique elements following a specific order. ——C++ Reference set的操作并不复杂,有以下几种 迭代器begin cbegin 返回指向...

发布 5条评论 2509次浏览

以“【模板】单源最短路径(弱化版)”为例 最短路径是图论当中的重点内容之一 这里我们借由洛谷上的一条模板题来理解一下什么是SPFA 首先明确,SPFA并不是一个算法的名字,这只是一个中国老师在1996年在Bellman–Ford算法基础...

发布 0条评论 1811次浏览

本篇将介绍在各类算法竞赛中应用广泛,也是最为基础的一种素数筛法,欧拉筛,他的本质是Eratosthenes筛的优化 在介绍欧拉筛之前,我们不妨先整体感悟一点就是素数的存在虽然是无序 的 (至少目前并没有有力的证明素数的分布存在一...

发布 0条评论 2055次浏览

map是STL的一个关联容器。 它提供一对一(其中第一个可称为关键字(Key),每个关键字只能在map中出现一次,第二个可称为该关键字的值(key_Value))的数据处理能力。 map的用法为 map< class _Key, class _Tp> 元素访...

发布 0条评论 2462次浏览
你好 No.65343