0 前言
总结一些最小生成树问题的常用模板
1 Kruskal
一种简单易实现的算法，基于贪心和并查集
1.1 原理
将所有的边按照边权从小到大排序，依次遍历每条边，如果两点未联通，就在生成树中加上这条边，选取 n−1n-1n−1 条边即可连成最小生成树
1.2 代码实现
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <bits/stdc++.h>using namespace std;const int N = 5e3 + 5;const int M = 2e5 + 5;int n, m;struct Edge{ int u, v, w; friend bool operator < (const Edge & x, const Edge & y) { return x.w < y.w; }} E[M];int ...
0 前言
总结一些最短路问题的常用模板 (这回是小坑了)
1 Floyd-Warshall - 多源最短路
基础的动态规划，经典的三重循环，最简单的最短路算法
1.1 原理
AcWing 854. Floyd求最短路
设 Fi,jF_{i,j}Fi,j 表示点 iii 到点 jjj 的最短路径，枚举中转点 kkk ，每次通过中转点更新最短路径，转移方程 Fi,j=min{Gi,j,Fi,k+Fk,j}F_{i,j} = min\left\{ G_{i,j}, F_{i,k} + F_{k,j} \right\}Fi,j=min{Gi,j,Fi,k+Fk,j} ，时间复杂度 O(N3)O(N^3)O(N3).
12345678910111213141516171819202122232425262728293031323334353637383940#include <bits/stdc++.h>using namespace std;const int N = 500 + 5;const int INF = 0x3f3f3f3f;int n, m, k;in...
0 前言
总结一些树上问题的常用模板 (感觉开了个大坑)
1 树的直径
1.1 树形 DP 求树的直径
设 DuD_uDu 表示从节点 uuu 出发走向以 uuu 为根的子树，能够到达的最远节点的距离，对于 uuu 的子节点 vi(1≤i≤ti)v_i(1 \leq i \leq t_i)vi(1≤i≤ti) ，有
Du=max1≤i≤tu{Dvi+edgeu,vi}D_u = \max_{1 \leq i \leq t_u}\{D_{v_i} + edge_{u, v_i}\}
Du=1≤i≤tumax{Dvi+edgeu,vi}
设 FuF_uFu 表示经过节点 uuu 的最长链的长度, 考虑 uuu 的两个节点 vi,vjv_i, v_jvi,vj，将其通过节点 uuu 连接即可，转移方程
Fu=max1≤j<i≤tu{Dvi+edgeu,vi+Dvj+edgeu,vj}F_u = \max_{1 \leq j < i \leq t_u}\{D_{v_i} + edge_{u, v_i} + D_{v_j} + edge_{u, ...
0 前言
总结一下三种求逆序对数的方法
1 定义
逆序对：序列 ana_nan 中，满足 i<ji < ji<j 且 ai>aja_i > a_jai>aj 的有序数对 (i,j)(i, j)(i,j).
2 算法
2.1 归并法
2.1.1 算法原理
本质就是CDQ分治，在归并排序合并的过程中处理逆序对数，计算右区间的每一位数字对已排好序的左区间的贡献
时间复杂度 O(nlogn)O(nlogn)O(nlogn).
2.1.2 代码实现
123456789101112131415161718192021222324252627282930313233343536373839404142#include <bits/stdc++.h>using namespace std;const int N = 5e5 + 5;int n;int a[N];long long mergesort(int *arr, int l, int r){ if (l == r) return 0; int mid...
题目描述
DESCRIPTION
Bessie is leading the cows in an attempt to escape! To do this, the cows are sending secret binary messages to each other.
Ever the clever counterspy, Farmer John has intercepted the first bib_ibi (1≤bi≤10,0001 \le b_i \le 10,0001≤bi≤10,000) bits of each of MMM (1≤M≤50,0001 \le M \le 50,0001≤M≤50,000) of these secret binary messages.
He has compiled a list of NNN (1≤N≤50,0001 \le N \le 50,0001≤N≤50,000) partial codewords that he thinks the cows are using. Sadly, he only kno...
题目描述
DESCRIPTION
Farmer John has always done his best to keep the pastures full of luscious, delicious healthy grass for the cows. He has lost the battle, though, as the evil milkweed has attained a foothold in the northwest part of his farm.
The pasture, as usual, is partitioned into a rectilinear grid of height YYY (1≤Y≤1001 \leq Y \leq 1001≤Y≤100) and width XXX (1≤X≤1001 \leq X \leq 1001≤X≤100) with (1,1)(1,1)(1,1) being in the lower left corner (i.e., arranged as a normal XXX,YYY coordina...
0 前言
说实话这东西看了一天也没有看懂，只能先贴模板了，以后再来填坑. 咕咕咕警告
1 算法原理
以上内容引用自 CSP-S 2021 第一轮 的最后一题.
2 例题&代码实现
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143#include <iostream>#include <cmath>using namespace std;const int MA...
题目描述
DESCRIPTION
Every year, Farmer John’s NNN (1≤N≤20,0001 \leq N \leq 20,0001≤N≤20,000) cows attend “MooFest”,a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a b...
0 前言
最近做到了很多关于求解最大子矩形的问题，写个博客稍微总结一下 (顺便整理一下模板)
1 一些基本定义
有效子矩形：内部不包含任何障碍点且边界与坐标轴平行的子矩形。
极大有效子矩形：不存在包含它且比它大的有效子矩形的有效子矩形。
最大(有效)子矩形：所有极大有效子矩形中最大的一个(或多个)有效子矩形。
2 两种常用的算法
算法1 基于障碍点的算法
例题1 奶牛浴场
题目描述
由于 John 建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John 决定在牛场中建造一个大型浴场。但是 John 的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John 希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于 Clevow 了。你还能帮助 Clevow 吗？
John 的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。
Clevow 当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。...
题目描述
DESCRIPTION
Keeping an eye on long term career possibilities beyond the farm, Bessie the cow has started learning algorithms from various on-line coding websites.
Her favorite algorithm thus far is “bubble sort”. Here is Bessie’s initial implementation, in cow-code, for sorting an array AAA of length NNN.
12345678sorted = falsewhile (not sorted): sorted = true moo for i = 0 to N-2: if A[i+1] < A[i]: swap A[i], A[i+1] sorted = false
Apparently, the “moo” command in cow-...