编程日记

模型复杂程度 一、常见衡量指标参数数量（Number of Parameters）模型包含的可学习参数越多，复杂度越高。 例如：线性回归：参数个数 = 特征维数 + 1 深度神经网络：每层权重矩阵大小 层数例子：ResNet-18（约1100万参数） vs. GPT-3（1750亿参数）模型容量（Model Capacity）…...

1.1 公式表达显示 代码行内公式 $数学公式$独立公式 $$数学公式$$1.2 上下标显示 代码$x^2$ $x^2$$x_2$ $x_2$1.3 括号显示 代码$\underbrace{yyyy}_{ \text{xxx} }$ $\underbrace{yyyy}_{ \text{xxxx} }$$\begin{cases} {df} & {g} \ {h} & {j} \ {k} & {a} \end{…...

最大流 Dinic 解 使用 \(\tt Dinic\) 算法，理论最坏复杂度为 \(\mathcal O(N^2M)\) ，例题范围：\(N=1200,\ m=5\times 10^3\) 。一般步骤：\(\tt BFS\) 建立分层图，无回溯 \(\tt DFS\) 寻找所有可行的增广路径。封装：求从点 \(S\) 到点 \(T\) 的最大流。 template<typen…...

最小割树 Gomory-Hu Tree 无向连通图抽象出的一棵树，满足任意两点间的距离是他们的最小割。一共需要跑 \(n\) 轮最小割，总复杂度 \(\mathcal O(N^3M)\) ，预处理最小割树上任意两点的距离 \(\mathcal O(N^2)\) 。 过程：分治 \(n\) 轮，每一轮在图上随机选点，跑一轮最小割后…...

最小割 基础模型：构筑二分图，左半部 \(n\) 个点代表盈利项目，右半部 \(m\) 个点代表材料成本，收益为盈利之和减去成本之和，求最大收益。 建图：建立源点 \(S\) 向左半部连边，建立汇点 \(T\) 向右半部连边，如果某个项目需要某个材料，则新增一条容量 \(+\infty\) 的跨部边…...

差分约束 给出一组包含 \(m\) 个不等式，有 \(n\) 个未知数的形如：$ \begin{cases} u_1-v_1\leq w_1 \u_2-v_2 \leq w_2 \ \cdots\ u_m -v_m\leq w_m\end{cases}\(的不等式组，求任意一组满足这个不等式组的解。\)\sf SPFA$ 解，\(\mathcal O(nm)\) 。参考 signed main() {int…...

图论常见结论及例题 常见结论要在有向图上求一个最大点集，使得任意两个点 \((i,j)\) 之间至少存在一条路径（可以是从 \(i\) 到 \(j\) ，也可以反过来，这两种有一个就行），即求解最长路；要求出连通图上的任意一棵生成树，只需要跑一遍 bfs ；给出一棵树，要求添加尽可能多的…...

最长路（topsort+DP算法） 计算一张 \(\tt DAG\) 中的最长路径，在执行前可能需要使用 \(\tt tarjan\) 重构一张正确的 \(\tt DAG\) ，复杂度 \(\mathcal O(N+M)\) 。 struct DAG {int n;vector<vector<pair<int, int>>> ver;vector<int> deg, dis;DAG…...

二分图最大匹配二分图：一个图能被分为左右两部分，任何一条边的两个端点都不在同一部分中。 匹配（独立边集）：一个边的集合，这些边没有公共顶点。 二分图最大匹配即找到边的数量最多的那个匹配。 一般我们规定，左半部包含 \(n_1\) 个点（编号 \(1 - n_1\)），右半部包含 \…...

最短路径树（SPT问题）定义：在一张无向带权联通图中，有这样一棵生成树：满足从根节点到任意点的路径都为原图中根到任意点的最短路径。 性质：记根节点 \(Root\) 到某一结点 \(x\) 的最短距离 \(dis_{Root,x}\) ，在 \(SPT\) 上这两点之间的距离为 \(len_{Root,x}\) ——则两…...

欧拉路径/欧拉回路 Hierholzers欧拉路径：一笔画完图中全部边，画的顺序就是一个可行解；当起点终点相同时称欧拉回路。有向图欧拉路径存在判定 有向图欧拉路径存在：\(\tt ^1\) 恰有一个点出度比入度多 \(1\) （为起点）；\(\tt ^2\) 恰有一个点入度比出度多 \(1\) （为终点）…...

无源汇点的最小割问题 Stoer–Wagner也称为全局最小割。定义补充（与《网络流》中的定义不同）： 割：是一个边集，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）。通过递归的方式来解决无向正权图上的全局最小割问题，算法复杂度 \(\mathcal O(VE + V^{2}\log V)…...

有一棵以 \(1\) 为根， \(n\) 个节点的树，每个节点有一个颜色白/黑。给定 \(q\) 组询问，每组询问给了一个 \(u\)，表示将 \(u\) 子树内的点的颜色全部翻转。每次操作后回答至少需要几条从根开始的链才能覆盖所有黑点覆盖。先来转化一下问题，题目问的其实就是有多少个节点 \(…...

染色法判定二分图 (dfs算法) 判断一张图能否被二分染色。 vector<int> vis(n + 1); auto dfs = [&](auto self, int x, int type) -> void {vis[x] = type;for (auto y : ver[x]) {if (vis[y] == type) {cout << "NO\n";exit(0);}if (vis[y]) con…...

链式前向星建图与搜索 很少使用这种建图法。\(\tt dfs\) ：标准复杂度为 \(\mathcal O(N+M)\)。节点子节点的数量包含它自己（至少为 \(1\)），深度从 \(0\) 开始（根节点深度为 \(0\)）。\(\tt bfs\) ：深度从 \(1\) 开始（根节点深度为 \(1\)）。\(\tt topsort\) ：有向无环图…...

一般图最大匹配（带花树算法） 与二分图匹配的差别在于图中可能存在奇环，时间复杂度与边的数量无关，为 \(\mathcal O(N^3)\) 。下方模板编号从 \(0\) 开始，例题为 UOJ #79. 一般图最大匹配 。 struct Graph {int n;vector<vector<int>> e;Graph(int n) : n(n), …...

平面图最短路（对偶图） 对于矩阵图，建立对偶图的过程如下（注释部分为建立原图），其中数据的给出顺序依次为：各 \(n(n+1)\) 个数字分别代表从左向右、从上向下、从右向左、从下向上的边。 for (int i = 1; i <= n + 1; i++) {for (int j = 1, w; j <= n; j++) {cin &…...

多源汇最短路（APSP问题） 使用邻接矩阵存图，可以处理负权边，以 \(\mathcal{O}(N^3)\) 的复杂度计算。注意，这里建立的是单向边，计算双向边需要额外加边。 const int N = 210; int n, m, d[N][N];void floyd() {for (int k = 1; k <= n; k ++)for (int i = 1; i <= n…...

最小生成树（MST问题） （稀疏图）Prim算法 使用邻接矩阵存图，以 \(\mathcal{O}(N^2+M)\) 的复杂度计算，思想与 \(\tt djikstra\) 基本一致。 const int N = 550, INF = 0x3f3f3f3f; int n, m, g[N][N]; int d[N], v[N]; int prim() {ms(d, 0x3f); //这里的d表示到“最小生成…...

缩点（Tarjan 算法） （有向图）强连通分量缩点 强连通分量缩点后的图称为 SCC。以 \(\mathcal O (N + M)\) 的复杂度完成上述全部操作。性质：缩点后的图拥有拓扑序 \(color_{cnt}, color_{cnt-1},…,1\) ，可以不需再另跑一遍 \(\tt topsort\) ；缩点后的图是一张有向无环图（…...