【题解】CF644B Processing Queries
www.luogu.com.cn
题目大意：
有一个队列，其中的每项工作 iii 都有两个值：最早可以处理的时间 tit_{i}ti 和处理所需要的时间 did_{i}di，等待队列中的数量不可以超过 bbb，求出每个工作完成时间（无法完成则输出 −1-1−1）。
模拟思路
这是一道结合了队列的模拟题，自然可以使用 queue\text{queue}queue 来做，但首先我们要搞清一下几点：
如何判断当前时间点有多少件事情可以完成。
如何根据队列中的等待数判断是否可以完成。
如何计算下一个事情前的完成时间。
我们可以定义一个一维数组 bg[N]\text{bg[N]}bg[N]，其中 bgibg_{i}bgi 表示第 iii 个事情时最早的可以做的时间，而由于每个事情都有自己的最早可处理时间 tit_{i}ti，因此 max(bgi−1,ti)\max(bg_{i - 1}, t_{i})max(bgi−1,ti) 即为第 iii 个事情的实际开始时间。显然可以得出转移方程：
bgi=max(bgi−1+di−1,ti)bg_{i} = \max(bg ...
【题解】P1990 覆盖墙壁
题目简述
www.luogu.com.cn
题目思路
这道题是很经典的动态规划题，最重要的是得出状态转移方程。
划分阶段
设定两个数组 fN,gNf_{N}, g_{N}fN,gN，分别表示填满前 2×i2 \times i2×i 格子的方案数以及填满前 i×2+1i \times 2+1i×2+1 格子的方案数。
答案即为 fnf_{n}fn。
状态转移方程
1×21 \times 21×2的瓷砖的摆放方式有两种：横着摆和竖着摆。
因此第一种瓷砖的状态转移方程为：
fi=fi−1+fi−2f_{i} = f_{i - 1} + f_{i - 2}
fi=fi−1+fi−2
由于L型瓷砖可以进行旋转摆放，故一共有3种可能：
通过两个L型瓷砖互补摆完。
仅在1×21\times 21×2的瓷砖后继续摆放。
故第二种瓷砖的状态转移方程为：
gi=gi−1+fi−1g_{i} = g_{i - 1} + f_{i - 1}
gi=gi−1+fi−1
综上所述
状态转移方程为：
fn=fn−1+fn−2+2×gn−2f_{n} = f_{n - 1} + f_{n ...
【题解】P1434 滑雪
题目简述
www.luogu.com.cn
给出一个 n×mn \times mn×m 的二维数组，求出最长的一条滑坡，使得这条滑坡的高度会依次减少。
解题思路
原始DFS
这是一道 DFS\text{DFS}DFS 搜索题，同样也可以使用 DP\text{DP}DP 来做。
这里用DFS。
可以先双重循环这个二维数组上的每个点，在每个点上进行周围四个点的搜索（同时也要注意边界条件）。
可以设定两个偏移数组如下。
1int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
1234567891011121314151617int dfs(int x, int y){ if (s[x][y]) return s[x][y]; s[x][y] = 1; for (int i = 0; i <= 3; i++) { int xx = dx[i] + x; int yy = dy[i] + y; if (xx & ...
【题解】P1219 八皇后问题
www.luogu.com.cn
基本思路
深度优先搜索（DFS）
由于题目数据很小（6≤n≤136 \le n \le 136≤n≤13），我们可以采用打表深度优先搜索的方式完成这道题。
定义四个布尔数组分别表示表格的行，列，两个对角线上是否有旗子存在。
如图所示。
抽象代码如下↓
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <bits/stdc++.h>using namespace std;const int N = 50;//常量记得开大一点int n, sum, a[N], b[N], c[N], d[N];// n:网格大小 sum:方案总数// a,b,c,d数组分别代表行，列，左下到右上的对角线，左上到右下的对角线void dfs(int i) // 核心代码{ if (i > n) // 判断是否到达边界 { if (sum <= 2) / ...
【常用技巧】快读/快输
使用 scanf / printf
在默认情况下，std::cin/std::cout 是极为迟缓的读入/输出方式，而 scanf/printf 比 std::cin/std::cout 快得多。
然而有的时候使用scanf/printf进行输入输出十分繁琐，因此我们可以采取取消同步流的方式直接使用std::cin/cout。
取消同步流传输
std::ios::sync_with_stdio(false)可以用来关闭stdio的兼容并解除std::cin和std::cout的绑定，从而达到较快的输入和输出。
但是在这样做之后要注意不能同时使用 std::cin 和 scanf，也不能同时使用 std::cout 和 printf，但是可以同时使用 std::cin 和 printf，也可以同时使用 scanf 和 std::cout。
std::cin.tie(0),cout.tie(0)可以用来解除std::cin和std::cout之间的绑定，从而进一步优化输入和输出。
但是要注意使用了这个以后不能再使用std::cout << endl原因在于endl不仅有换行的功 ...
【笔记/模板】最小生成树
www.luogu.com.cn
概念/定义
一个连通图的生成树是一个极小的连通子图，它包含图中全部的 nnn 个顶点，但只有构成一棵树的 n−1n-1n−1 条边。而最小生成树就是一个带权图的生成树，并且使得原图中边的权值最小的生成树 ，所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。
思路（Kruskal适用于稀疏图，Prim适用于稠密图）
Kruskal 算法
整体思路：
Kruskal 是一种使用贪心 + 排序+并查集的最小生成树算法，通过每两个点之间的最小距离累加并且将两个点合并，最终生成一种生成树的算法。
时间复杂度：
O(mlogm)O(m \log m)O(mlogm)（其中 mmm 点表示边数）。
代码实现：
1234567891011struct Edge{ int u, v, w; // 存下入边，出边，权值 bool operator < (const Edge &rhs) const // 重载运算符，将权值为第一关键词非降序排序 { if (w != rhs.w) return ...
【笔记/模板】拓扑排序
www.luogu.com.cn
拓扑排序
定义与实现思路
拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
根据定义可知，我们可以使用队列+BFS的方式求出一个图的拓扑序列，方法如下：
存图的时候记录下每个点的前驱数（即入度）。
从图中选择一个 没有前驱（即入度为 000）的顶点并输出，将其加入队列当中。
重复步骤 222 直到队列中的元素个数为 000 时，停止程序。
tips\bold tipstips：通常，一个有向无环图可以有一个或多个拓扑排序序列。
代码实现
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849// Problem: B3644 【模板】拓扑排序 / 家谱树// C ...
【笔记/模板】树状数组
原理解释
树状数组是一种通过前缀和和差分的思想所进行的维护数组，从而以 O(logn)O(\log n)O(logn) 的时间复杂度进行修改和查询。
一共有四种修改和查询的方式，分别是：
单点修改 +++ 区间询问
区间修改 +++ 单点询问
单点修改 +++ 区间询问
（二维）区间修改 +++ 区间询问
其中利用树状数组可以高效而简洁地处理第二、三个问题，第四个问题推荐使用【模板/笔记】线段树。
查询
查询可以计算左右区间的总和，通过它们的前缀和相减求出区间和。通过上图可以发现，如果要求 sum7sum_{7}sum7 的值，可以发现 sum7=tree7+tree6+tree4sum_{7} = tree_{7} + tree_{6} + tree_{4}sum7=tree7+tree6+tree4，而 7,6,47,6,47,6,4 之间有什么关联呢？
将其转化为二进制可以看出：7=(111)2,6=(110)2,4=(100)27=(111)_{2},6=(110)_{2},4=(100)_{2}7=(111)2,6=(110)2,4=(10 ...
【笔记/模板】ST表/RMQ
RMQ（区间最值问题）
Range Maxinum/Mininum Query（又称ST表）可以通过dp+倍增预处理的方式从而达到 O(nlogn)O(n \log n)O(nlogn) 的构建预处理，O(1)O(1)O(1) 的查询。
初始化
我们可以通过先定义一个二维数组 fi,jf_{i, j}fi,j表示从第 iii个数开始的区间大小为 jjj 的最值。而由于一个区间的最值 fi,jf_{i, j}fi,j 可以通过这个区间的两部分 fi,j−1和fi+2j−1,j−1f_{i, j - 1} 和 f_{i + 2 ^ {j - 1}, j - 1}fi,j−1和fi+2j−1,j−1得到，从而可以得到状态转移方程：
fi,j=max/min(fi,j−1,fi+2j−1,j−1)f_{i, j} = \max/\min(f_{i, j - 1}, f_{i + 2 ^{j - 1}, j - 1})
fi,j=max/min(fi,j−1,fi+2j−1,j−1)
数组的第一维范围为数据的最大范围 nnn，第二维为数据最大范围的 log2n\log_{2 ...
【笔记/模板】Johnson全源最短路
模板题目
www.luogu.com.cn
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114// Problem: P5905 【模板】全源最短路（Johnson）// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P5905// Memory Limit: 128 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>using namespace std;t ...