Thy's Blog

题目简述 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 & ...

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(mlog⁡m)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(log⁡n)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 ...

RMQ（区间最值问题） Range Maxinum/Mininum Query（又称ST表）可以通过dp+倍增预处理的方式从而达到 O(nlog⁡n)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，第二维为数据最大范围的 log⁡2n\log_{2 ...

模板题目 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 ...

原理解释 Dijkstra算法是通过贪心+BFS+动态规划实现的，可以用来计算单个点（源点）到其余任一点的距离大小。 Dijkstra算法的实现分为以下几步： 定义并初始化数组dis[N]，其中 disidis_{i}disi​ 表示源点当前距离 iii 点的最短距离，再定义一个 boolboolbool 数组 vis[N]， visivis_{i}visi​ 代表第 iii 个点是否被拓展过（即是否达到了最优解）。 从未被拓展的点中找出一个离源点最近的点 xxx（此时它已经是最优解），通过这个点依次松弛和它联通的每一个点距离源点的距离，同时将所松弛的点加入到队列当中。 等到队列中没有元素存在之后，结束函数，此时 dis[N] 中的每个点 disidis_{i}disi​ 即代表着距离源点的最小距离。 代码实现 朴素法 123struct Edge { int x, w; }; // x表示出点，w表示权值.vector<Edge> g[N]; //存图数组int dist[N]; //d[i]表示st距离i点的距离大小 12345678 ...

单调栈 定义 单调栈即满足单调性的栈结构。通过只在一端进出，从而维护一个数在前 / 后的第一个大于或小于它的数。 操作 / 方式 首先按照特定的顺序遍历。 如果要求出最小值，就要将栈顶大于入列元素的所有数全部弹出。 此时候的栈顶就是直到当前下标的答案。 加入这个元素并且继续更新。 代码 结构体 + STL模板 12345678910111213141516171819int a[N], ans[N];struct Node { int val, idx; };stack <Node> stk; signed main(){ // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = n; i >= 1; i--) { while (!stk.empty() & ...