Llf's blog

分类 OI笔记 下的文章

May 9, 2018

基础数论学习总结

原本打算先学Splay的,但想到提高组一般不考,而且我其它东西还差的多,就先把基础数论的东西复习一下,并且加深一下难度,还做了n多道水题,虽然主要是之前没过的。 1.整除 这里就把整除的性质列一下: 如果 $a \mid b$ 且 $b \mid c$,那么 $a \mid c$ $a \mid b$ 且 $a \mid c$ 等价于 $\forall x,y$,有 $a \mid (b...
April 26, 2018

点分治总结

我自己感觉点分治是一种比较玄学神奇的算法,感觉自己也只是理解了一点皮毛而已。这里就谈谈点分治的实现方法和一些运用。 方法 点分治其实是将一棵树的点不断分为多棵子树,分别得到子树节点到子树根的距离来进行处理。 既然要有一个点为根节点,那么应该选取哪一个点呢? 既然要向下分治,如果把一个原来的叶节点作为分治的根节点,那么遍历每一个点的时间开销是非常大的。然而如果这个点的左右子树都达到最大,那么...
April 21, 2018

二分图匹配

我是看这篇学懂的,真的写得很好,所以我就不在这里总结了,只发个模板 https://blog.csdn.net/dark_scope/article/details/8880547 模板题:洛谷 P3386【模板】二分图匹配 #include<bits/stdc++.h> using namespace std; bool edge[1005][1005]; bool used[...
April 16, 2018

树链剖分总结

作为一个上个月刚学完线段树的蒟蒻,看Splay又看不懂,便直接跳着来学树剖了。又在一个博客上看到说学树剖之前最好还要把LCA给学了,便去花了一天学了一个Tarjan求LCA(然而后来发现并不怎么需要),然后是几乎照着别人的代码把树剖抄懂的。在这里我就讲一下我理解的树剖。 准备工作 链表/链式前向星 线段树/树状数组/Splay等可以维护一段数据的数据结构 LCA (其实只涉及到一些思想,...
April 10, 2018

LCA问题总结

概述 最近公共祖先(LCA)问题指的是在一棵树中,求出任意两个点的最近的公共祖先。如在下图中: 2号节点和1号节点的LCA是4,3号和2号的LCA也是4. 求LCA的方法主要有:暴力,倍增,RMQ和Tarjan。 这篇文章以洛谷P3379 【模板】最近公共祖先(LCA)为例。 Tarjan算法 Tarjan算法能够通过dfs将树上节点信息和查询的信息一次性解决,但是无法应对存在修改的情况,...
April 9, 2018

RMQ问题_ST表总结

RMQ问题 RMQ问题是指多次询问一个区间中最小或最大值的问题。但是因为不包括修改,只涉及离线操作,所以线段树或者树状数组显得有一些多余了。而且数列中的元素个数可能非常大,像线段树开四倍空间肯定是要MLE的。这里介绍一种高效的ST表来解决这种问题。 ST表 我的理解:ST表运用动态规划和二分的思想来完成。 ST表查询问题包含初始化和查询操作,其中初始化的时间复杂度为$O(n\times \l...
February 7, 2018

几种排序方法总结

冒泡排序 方法 第一次将每一个元素和它的后一个元素比较大小,如果不满足顺序则交换,这样即可确定最后一个数的位置。然后再从头开始,可以确定倒数第二个数的位置。循环n次后即可完成排序。因为每一轮排完序后都会确定一个,即“冒”出来一个,故被称作冒泡排序。 时间效率:$O(n^{2})$ 代码 以 洛谷 P1116 车厢重组 为例 #include<bits/stdc++.h> usi...
February 6, 2018

拓扑排序

概念 拓扑排序是一种可以将有先决条件(即必须将a、b排在前面后再排c,缺一不可)的数据变得有序的一种排序方法。拓扑排序仅可在有向无环图中使用,同时可以判断图中是否有环。因为顺序不同,拓扑排序得到的答案可能不同。 思路 因为排序是有先决条件的,所以可以将要有先决条件的个数(在图中即为入度)记录下来,每满足一个就减一,直到个数为0便可以将其放入序列中。 手动实现 如果我们有如下的一个有向无环图,...
February 6, 2018

最小生成树

概念 最小生成树即为无向图中结点构成的树中各边权值之和最小的树,可以有多种情况。一般用Kruskal(克鲁斯卡尔)算法或Prim(普里姆)算法求出。 Kruskal算法 方法 可以将Kruskal算法理解成对边的贪心算法。 1.将路径用邻接表存储,存储的值为起点、终点和权值; 2.将邻接表按照权值为关键字排序; 3.从最小权值的边开始循环,每连接起两个结点就把它们并到同一个集合(并查集实现)...
December 25, 2017

前缀和差分

前缀和差分用于在多次求数据中选取一部分的和,可分为一维前缀和和二维前缀和 一维前缀和 运用递推,将数组每一个元素替换为到这个元素的所有元素之和,如 1 3 4 3 2 5 在处理后变为 1 4 8 11 13 18 如何需要求出数组第X位到第Y位的和,直接用f[y]-f[x-1]即可 二维前缀和 与一维前缀和同理,只是f[a][b]的值变为从s[1][1]到这个点的矩阵内所有数的和,如s...