coder-River

归纳

题解(82)

/ 注册

全部文章 / 归纳（共12篇）

[图论] 最大匹配问题归纳来自专栏

一、定义即在一个二分图中，找到最大的匹配对数。每个点只能最多和另外一个点配对。二、情景为了方便理解，这里考虑一下最大匹配场景：有一列男生1..n，还有一列女生女生n + 1..n + m。即结点分开存；愿意配对的男女会有边相连；要求出男女配对的最大匹配数目。三、解析有两种方法可以...

2020-09-26

0 829

[图论][经典] 常见的图论方法归纳来自专栏

一、dfs 1. 定义 dfs，即深度优先搜索。顾名思义，即尽可能递归到达最深处，然后再回溯，以此类推，直到遍历完整个图。 2. 解析通过递归实现。主要用于解决找迷宫路径等问题。dfs代码比bfs简单。要领：用vis数组维护是否走过，记得清零；dfs中continue的条件分三类：出界、已走...

2020-09-24

1 516

[图论] 复杂的图论问题归纳来自专栏

一、求最近公共祖先结点（LCA） 1. 定义 LCA（Lowest Common Ancestors），即最近公共祖先，是指在有根树中找出某两个结点u和v最近的公共祖先结点。 2. 解析这里只说一种我个人比较喜欢的在线算法：欧拉序 + RMQ 时间复杂度：预处理 O(n+nlgn)，查询只需要...

2020-09-13

0 797

[区间问题] 树状数组与线段树归纳来自专栏

一、树状数组 1. 定义用一个数组C[maxn]模拟树状结构，来表示原数组A[maxn]的区间信息。各操作的复杂度为O(lgn)。 2. 解析 lowbit(x) 指一个数x的二进制中，最靠右的1的权值大小。如lowbit(6)=2^1, lowbit(7)=2^0，lowbit(8)=8。树...

2020-09-13

0 908

[动态规划][经典] 常见的动态规划问题归纳来自专栏

最长上升子序列（LIS） 1. 定义给出一个序列a[1...n]，要求你求出其中最长的递增子序列的长度。 2. 简单的 O(n^2) 算法原理：设 dp[i] 为把下标i作为最长上升子序列结尾位置的最大长度，则 dp[i] = max(dp[1..i]+1)，所有dp[i]初始为1. 模板...

2020-09-13

0 592

[动态规划] 数位dp方法归纳来自专栏

一、定义求出在给定区间 [A,B] 内，符合条件 f(i) 的数i的个数。条件f(i)一般与数的大小无关，而与数的组成有关。由于数是按位dp，数的大小对复杂度的影响很小。简单来说，就是解决一些与区间中的数字的计数问题，计数条件一般与数的组成有关。二、状态量一般采用记忆化搜索的方式来实现dp，...

2020-09-13

0 864

[数学][经典] 常见的数学方法归纳来自专栏

基本说明由于数学类方法经常性混合使用（比如组合数+快速幂），因此例题在最后统一给出。一、最大公约数和最小公倍数（gcd） 1. 定义没啥好说，大家都懂。最大公约数 gcd(a,b) ，最小公倍数 lcm(a,b) 。 2. 解析求最大公约一般用辗转相除法，最小公倍数可以由最大公约数导出： ...

2020-09-10

0 620

[图论] 最短路问题归纳来自专栏

基本原则首先看题目n的数量级，当 n<1000 时，可以使用 [Floyd算法] 快速秒杀几乎所有题型否则若题目中所有边全为正权，则使用 [Dijkstra算法] 否则当出现负权时，使用 [spfa算法] 注意一些隐蔽的最短路问题，比如题目会换一种问法。详见最短路的各种变形题。...

2020-09-04

0 1115

[枚举] 暴力求解之枚举方法归纳来自专栏

一、枚举排列 1. 定义枚举出一个序列a[maxn]的所有排列。 2. 解析枚举排列最简单的方法是运用STL的 next_permutation函数. 3. 模板 int a[maxn]; int main(){ ...... sort(a, a + n); ...

2020-09-04

1 1300

[经典] 常见的高效算法归纳来自专栏

一、滑动窗口 1. 定义滑动窗口法（又叫双指针法），即用i,j双指针（一般用下标）对数组进行遍历，同时要需要一个额外的比如vis数组维护窗口中的元素信息，是一种O(n)的扫描方法。 2. 解析一般比较常见的问题就是，维护窗口中的元素各不相同。既可以用一个vis[maxn]数组来表示窗口中是否存...

2020-09-04

0 485