一、概述   DFS只能求出来是否能从起点到终点，不能求出来最短距离。   DFS一般代码比BFS要短一些因为不用维护队列，缺点是递归太深容易爆栈，栈空间应该是1MB左右         1、DFS——连通型   包括在BFS中见到的Flood Fill类型、图和树的遍历   一般题上是问能否从A点走到B点，或者从这个点出发能到达多少个符合要求的点   这类题一般是从棋盘上一个点到另一个点，每个点只需要走一遍，所以不需要恢复现场。      例题：1113. 红与黑 - AcWing题库   代码模板：   #include<iostream> #include<cstrin...

一、概述   基本的搜索一般分为bfs和dfs，在都可行的前提下，最好选择bfs，因为dfs递归时可能会爆栈，而且bfs的思路和过程可能会清晰一些因为不用递归，一般是维护队列就行   1、Flood Fill算法      思路：   可以在线性的时间内，找到某个点所在的连通块。  在一次宽搜的过程中，可以把所有符合性质的点组成的连通图标记。 一般分为4连通(上下左右)和8连通(周围8个格子)。     具体过程就是将符合条件的点入队,然后依次遍历这个点的几个方向,判断新的点是否满足条件,满足的话就入队继续更新。   一般条件就是是否出界,是否已经遍历过了,是否符合题目的特殊要求      代...

一、tmux      功能：      (1) 分屏。     (2) 允许断开Terminal连接后，继续运行进程。 结构：     一个tmux可以包含多个session，一个session可以包含多个window，一个window可以包含多个pane。     实例：         tmux:             session 0:          ...

一、树的三种遍历   1、先序遍历：根左右   这个没啥说的，和人的思考模式一样。先根结点再左儿子在右儿子         2、中序遍历：左根右   对于每个”三个点“的结构，先看左儿子，再看根，再看右儿子，如果左儿子下面还有儿子，就看左儿子下的”三个点“结构，不完整的地方就当有，然后跳过就行了      3、后序遍历：左右根     代码模板：   #include<iostream> using namespace std; int tree[10]={0,1,2,3,4,5,6,7,8,9};//从0开始存，要是从1开始存，左儿子就是2*x，右儿...

一、文件系统   1、一些文件   （1）根目录 /   （2）常用文件夹   bin：各种可执行文件   etc：存储各种配置   var：存各种日志   lib：存静态链接库   proc：存计算机的信息   home：存用户的   home 里acs 再里 main.cpp     2、在Linux中描述路径   分为两种   （1）绝对路径：从根目录开始描述，即从/开始       如/home/acs/main   （2）相对路径：在当前的文件下开始描述       例如：当前有home--acs--tem--main.cpp    ...

一、区间选点问题   1、区间问题   1、思路    给定N个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。   将每个区间按照右端点从小到大排序，然后从前往后依次枚举每个区间。   如果下一个区间和当前区间没有交点，就新开一个，点+1   如果有交点，直接过。      当一个问题是单峰的，可以用贪心，因为贪心选的是当前的最优解，   如果是多峰，可能有问题，即局部最优解不一定是全局最优解          2、代码模板：   #include<iostream> #include<algorit...

1、思路            2、代码模板：   #include<iostream> #include<cstring> using namespace std; const int N=310; int n,m; int h[N][N]; int f[N][N]; int dx[4]={-1,0,1,0};//上下左右移动 int dy[4]={0,1,0,-1}; int dp(int x,int y)//求以(x,y)为起点的状态 { &nb...

1、思路            2、代码模板：   #include<iostream> #include<cstring> using namespace std; const int N=6010; int n; int happy[N]; int h[N],e[N],ne[N],idx; int f[N][N]; bool has_father[N]; void add(int a,int b)//邻接表存树 {   &nbs...

一、蒙德里安的梦想   1、思路   当我们把所有的横向小方格放好后，我们竖向放的小方格就只有一种摆放情况   f[i][j]:这里的i是第i列，j存的是当前的第i列的所有小方格的状态，j用二进制表示，每一位代表当前列的每一行小方格的状态，j的范围为0~2^n-1           1是代表在第i-1列的这一行有一个横向的小方块，小方块的末端在i列，我们才记为1。           0一种是没有小方块，一种是横向小方块的前端。   举例说明：  &nb...

一、Nim游戏   1、思路   公平组合游戏：   （1）2名玩家交替行动   （2）再游戏进行的任意时刻，可以执行的合法行动与轮到谁无关   （3）不能行动的玩家判负      先手必胜状态：可以走到某一个先手必败状态   先手必败状态：走不到一个先手必败状态   对于每堆石子，a1,a2,a3……an为每堆石子个数   结论：   当    a1^a2^a3…………^an=0    则是先手必败状态   当    a1^a2^a3…………^an=x!=0   则是先手必胜状态       ...

1、原理   图来自Cloudddddd，   不想码字了，偷个图好了。。。         一共m个集合   我们将m用二进制表示，哪一位是1就代表有这个集合，0就代表没这个集合           2、代码模板：   #include<iostream> using namespace std; const int N=20; typedef long long ll; int n,m,p[N]; int main() {     scanf("%d...

1、思路   (1)当n为质数时，可以用快速幂求逆元：  a / b ≡ a * x (mod n) 两边同乘b可得 a ≡ a * b * x (mod n) 即 1 ≡ b * x (mod n) 同 b * x ≡ 1 (mod n) 由费马小定理可知，当n为质数时 b ^ (n - 1) ≡ 1 (mod n) 拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n) 故当n为质数时，b的乘法逆元 x = b ^ (n - 2)     (2)当n不是质数时，可以用扩展欧几里得算法求逆元：  a有逆元的充要条件是a与p互质，所以gcd(a, p) = 1 假设a的逆元为...

一、组数多，a,b范围较小——O(n^2)   1、思路   正常的求解公式是                              我们通过公式                    ...

1、思路   对于一个多元线性方程组，通过高斯消元的方式，可以在O（n^3）的时间复杂度解决   通常解有三种情况，   无解，   无穷多组解，   唯一解。      例如求解          ……         解决的方式是通过初等行列式变换   （1）把某一行乘一个非0的数   （2）交换其中两行   （3）把某行的若干倍加到另外一行   这三种操作不会改变解的结果。      通过操作将它变为倒三角形式                    ...