coder-River

分类

归纳(12) 题解(82)

/ 注册

TA的专栏 98篇文章 0人订阅

Re：从零开始的刷题生活

85篇文章 992人学习

Re：从零开始的归纳时间

13篇文章 1282人学习

全部文章（共94篇）

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

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

2020-09-26

0 822

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

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

2020-09-24

1 489

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

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

2020-09-13

0 790

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

一、树状数组 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 824

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

最长上升子序列（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 604

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

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

2020-09-13

0 840

Nowcoder 进来学习树的重心求法来自专栏

一、题意一棵树有n个结点（n<=1e6），每个结点的权重为其深度，根节点深度为0。给这棵树选一个根节点，使得它的权重和最小。二、解析即使没学过树的重心这个概念，凭直觉就能感受到，以“重心”为根节点的树的权重和应该是最小的。事实上也是如此。树的重心：定义：对于一棵树的每一个结点u，它们...

2020-09-10

0 493

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

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

2020-09-10

0 607

Nowcoder 使用费马小定理求解带模的组合数来自专栏

一、题意求以x结尾的长度为l的不下降正整数数列一共有多少个。对911451407取模。输入共有kase（kase<=1e5）组数据，每组数据满足x、l<=1e6。二、解析这是一道数学类题目。一开始看到题目的第一直觉是用动态规划，即dp[l][x]表示以x为结尾的长度为l的不下降正...

2020-09-10

1 910

Poj 3159 进来学习差分约束问题以及利用链式向前星加快读图来自专栏

一、题意输入n（n<=3000）和m（m<=150 000）表示有n个小朋友进行分糖。然后是m对关系，(A B w)表示A的糖果最多比B少w个。求1号和n号最多能差多少个糖果。二、解析这是一道差分约束问题，将原题目转化一下就是：给出n个数的m个约束关系，每个关系(A B w)表示...

2020-09-05

0 560