一、dfs 1. 定义 dfs，即深度优先搜索。顾名思义，即尽可能递归到达最深处，然后再回溯，以此类推，直到遍历完整个图。 2. 解析 通过递归实现。主要用于解决找迷宫路径等问题。dfs代码比bfs简单。 要领：用vis数组维护是否走过，记得清零；dfs中continue的条件分三类：出界、已走过、不是所求。不要遗漏了。 3. 模板 const int Fx[8][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}}; // 方向 string a[maxn]; // 记录地图 boo...

一、求最近公共祖先结点（LCA） 1. 定义 LCA（Lowest Common Ancestors），即最近公共祖先，是指在有根树中找出某两个结点u和v最近的公共祖先结点。 2. 解析 这里只说一种我个人比较喜欢的在线算法：欧拉序 + RMQ 时间复杂度：预处理 O(n+nlgn)，查询只需要O(1) 原理：欧拉序 就是在dfs遍历一棵树时经过的结点序列（包括回溯时经过的结点），显然两个结点u、v的最近公共祖先就是 欧拉序中 区间[u, v] 中深度最小的结点。（其中u、v指的是u、v在欧拉序中的第一次出现，即递归过程中的记录）因此我们只需要通过一遍dfs得到欧拉序euler[2 * ...

一、树状数组 1. 定义 用一个数组C[maxn]模拟树状结构，来表示原数组A[maxn]的区间信息。各操作的复杂度为O(lgn)。 2. 解析 lowbit(x) 指一个数x的二进制中，最靠右的1的权值大小。如lowbit(6)=2^1, lowbit(7)=2^0，lowbit(8)=8。 树状数组就是用一个C[maxn]数组来存放原数组A[maxn]的去区间信息。具体而言，C[x]存放了从A[(x-lowbit(x))...x]区间中各元素之和。 A[0]为0，不存放有效值。 [单点更新 区间查询] 求A[1...x]的区间和就需要求出它所对应的那几个C[j]区间之和，这几个区间通过l...

一、 题意 一只青蛙当看的当前景点比前面看过的景点差的时候，青蛙就会说“不开心”为了避免这只青蛙说“不开心”，并且使青蛙看的景点尽量的多，所以他请你帮忙给他安排一条线路，使青蛙可以看到尽量多的景点，并且不走回头路。 第一行为一个整数n，表示景点的数量，接下来n行，每行1个整数，分别表示第i个景点的质量。 一个整数，表示青蛙最多可以看到几个景点。 二、解析 最长上升子序列板子题，顺便复习一下。 有用动态规划的O(n^2)方法和用贪心+二分的O(nlgn)方法，两个都可以的。 三、代码 动态规划 #include <iostream> using namespace std; co...

最长上升子序列（LIS） 1. 定义 给出一个序列a[1...n]，要求你求出其中最长的递增子序列的长度。 2. 简单的 O(n^2) 算法 原理：设 dp[i] 为把下标i作为最长上升子序列结尾位置 的最大长度，则 dp[i] = max(dp[1..i]+1)，所有dp[i]初始为1. 模板： int n, num[maxn], dp[maxn]; // num[maxn]存放了序列，dp[i]表示以a[i]为结尾的最长子序列长度 int main() { ...... int ans = 0; for(int i = 1; i <= n; i +...

一、题意 给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。输入一行两个整数a、b，含义如上所述。输出一行10个整数，分别表示0-9在[a,b]中出现了多少次。 二、解析 看到区间、询问次数、数码（数的组成），应该马上想到用数位dp。 0-9分别跑一次数位dp，这样每一次就是一个带前导0判断的数位dp的板子题了！ 三、代码 #include <iostream> #include <cstring> using namespace std; using ll = long long; ll a[20], dp[20][20...

一、题意 游戏规则是这样的： 一个人报出一个起始数，接下来按照逆时针的顺序轮流报数，如果碰到数是7的倍数或含有7，则拍手，下一个人接着报数。直到有一个人报错了数字或者没有及时拍手为止。 输入两个整数m和n。(1 ≤ m, n ≤ 10^12)输出一个整数，表示m以后第n个需要拍手的数字。 二、解析 由于题目中涉及到计数的问题，并且还涉及到数的组成问题，因此考虑用数位dp来解决。 判断m以后的第n个是比较困难的，而用数位dp计算一个数字是第几个是比较简单的，也因此判断一个数是否是m之后的第n个也是简单的：只需要判断这个数和m的排位之差是否为n即可。于是我们就用二分答案来枚举答案，然后用数位d...

一、定义 求出在给定区间 [A,B] 内，符合条件 f(i) 的数i的个数。条件f(i)一般与数的大小无关，而与数的组成有关。由于数是按位dp，数的大小对复杂度的影响很小。 简单来说，就是解决一些与区间中的数字的计数问题，计数条件一般与数的组成有关。 二、状态量 一般采用记忆化搜索的方式来实现dp，dp的状态经常包括pos、pre、cnt、lead、limit这几项： pos：当前处理的是数位的第几项，一般从高往低走 pre：当前位的前几位的状态，由于数位dp解决的大多是数字组成问题，所以经常要比较当前位和前一位或前几位的关系（根据题意而定） cnt：随着pos的前进需要维护的一些答案值/计...

一、题意 一棵树有n个结点（n<=1e6），每个结点的权重为其深度，根节点深度为0。给这棵树选一个根节点，使得它的权重和最小。 二、解析 即使没学过树的重心这个概念，凭直觉就能感受到，以“重心”为根节点的树的权重和应该是最小的。事实上也是如此。 树的重心： 定义：对于一棵树的每一个结点u，它们的最大子树的结点数记为dp[u]。所有的结点中，dp最小的那个结点就是重心。 性质： 重心到所有节点的距离和最小（边权为1） 两棵树合并，新的重心在两棵树重心的路径上 一棵树添加或删除一个节点，重心最多移动一条边的位置 重心的最大的子树的节点数最小 三、代码 #include <iostr...

基本说明 由于数学类方法经常性混合使用（比如组合数+快速幂），因此例题在最后统一给出。 一、最大公约数和最小公倍数（gcd） 1. 定义 没啥好说，大家都懂。最大公约数 gcd(a,b) ，最小公倍数 lcm(a,b) 。 2. 解析 求最大公约一般用辗转相除法，最小公倍数可以由最大公约数导出： 同时注意为了防止a*b溢出，最终我们最小公倍数用下述公式求解： 3. 模板 LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); } 二、扩展欧几里得算法（exgcd） 1. 定义 上面说的求最大公约数的方式实际上叫欧几里得算...

一、题意 求以x结尾的长度为l的不下降正整数数列一共有多少个。对911451407取模。输入共有kase（kase<=1e5）组数据，每组数据满足x、l<=1e6。 二、解析 这是一道数学类题目。一开始看到题目的第一直觉是用动态规划，即dp[l][x]表示以x为结尾的长度为l的不下降正整数数列个数。则由dp[l][x]=∑dp[l-1][1...x]。然而由于x、l<=1e6，我们第一没有足够的空间开数组，第二时间复杂度也一定为超时。 于是我们考虑在一个x*l的平面上考虑递推式dp[l][x]=∑dp[l-1][1...x]的含义，即每一个（x,l）格子的数字等于它的左边...

一、题意 输入n（n<=3000）和m（m<=150 000）表示有n个小朋友进行分糖。然后是m对关系，(A B w)表示A的糖果最多比B少w个。求1号和n号最多能差多少个糖果。 二、解析 这是一道差分约束问题，将原题目转化一下就是：给出n个数的m个约束关系，每个关系(A B w)表示B-A<=w，问N-1<=多少? 即N-1的最大值为多少？ 问最大值的差分约束问题可以转化为最短路问题解决。 原理：以问最大值为例，问x-y<=多少时，肯定是通过若干B-A<=w的约束条件才可能获得，而B-A<=w这一不等式可以理解为d[B]<=d[A]+w，...

一、题意 每组数据有20个城市，给出每个城市与之相邻的城市，距离为1，不相邻的城市认为不可达。然后有q个询问，每次询问任意两个城市之间的距离。 二、解析 由于要询问任意两个城市之间的距离，因此这是一个多源最短路问题，即需要得到每两个点之间的最短路。这样的问题只能使用Floyd算法。算法复杂度为O(n^3)，在数据量小的时候非常方便。 PS: 这题的输入搞得相当复杂orz....我主要是想复习一下Floyd的模板而已.... 三、代码 #include <iostream> #include <iomanip> #include <cmath> using n...

一、题意 农夫有n块田地, 编号 1...n(1<=N<=500)，田地间有m1条双向路径，每条路径有一个经过所需要的时间wi。同时有m2个单向虫洞, 每条虫洞走完后时间倒回wi。问农夫是否能在田地中遇到以前的自己。 二、解析 这道题的情景非常有意思，m1条双向路径的权值为w，而m2条虫洞则相当于单向的负权路径，这样题目实际上就是判断图中是否存在负环，若存在，则农夫可以沿着负环一直走，时间将一直倒退，直到遇到以前的自己😀. 带负权的最短路径问题，可以使用Bellman-Ford或它的优化版本，即spfa算法。spafa算法能解决带负权的单源最短路问题，同时判断是否存在负环。最...