01背包问题 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，输出最大价值。 原题：AcWing 2。 动态规划最入门的问题，我们开辟一个二维数组 f[i][j]，它的含义是在前 i 个物品中在体积最大为 j 的基础上的最优解。 可以得到状态转移方程：f[i][ ...

简介 二分图指的是可以把点放到两个集合中，并且集合中不存在边。染色法可以判断一个图是否为二分图，匈牙利算法可以求出二分图最大匹配。匹配指的是二分图中任意两条边都不依赖于同一个顶点的一个子图，简而言之就是在这两边连线不能重复连同一个点，求这些连线的个数。 染色法判定二分图 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。 请你判断这个图是否是二分图。 用 DFS 染色，每个节点和它 ...

简介 最小生成树问题是指用图中所有节点构造一个边权重之和最小的树，可以用 Prim 算法和 Kruskal 算法解决稠密图和稀疏图的最小生成树问题。 Prim 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。 求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。 Prim 算法适用于稠密图，与 Dijkstra 算法思想一致，基本思路如下 ...

简介 对于最短距离问题，一共有如下几种算法： Dijkstra 算法是用来计算单源正权最短路算法，它的朴素版适用于稠密图，复杂度 O(n2)O(n^2)O(n2)；堆优化版适合稀疏图，复杂度 O((n+m)log⁡n)O((n+m)\log n)O((n+m)logn)。 Bellman-ford 算法用来解决**（有边数限制）的含负权最短路问题**，如果有边数限制一般就只能用此算法求解，复杂度 ...

Trie 树是用来存储和查找字符串或数字等构成元素不多的数据结构，多用来匹配特定前缀。

在 C++ 中用数组来模拟单双链表，这样的方式也被称为静态链表，下面以两例题记录 C++ 中的链表应该如何定义和使用。

前缀和用来求一个区间内的和，差分用来对一个区间加减常数的操作减少复杂度，利用了高中数学中学过的数列前N项和的性质。

配置文件 本文用 Dayjs 来处理日期。当然，完全可以用原生 Date，但我不想把时间浪费在处理日期上面。 我使用的是 butterfly 主题。如果读者正在使用别的主题，请查阅对应官方文档寻找如何插入自定义标签与自定义页脚信息。 在主题配置文件（即_config.butterfly.yml）中引入： 12345inject: bottom: - <script src=" ...

弧微分 这里简要给出过程，虽然不是特别严谨，但理解起来容易就好。 对于上图可以得出： ΔsΔx=∣AB⏠∣Δx=∣AB⏠∣2∣AB∣2⋅∣AB∣2(Δx)2=∣AB⏠∣2∣AB∣2⋅(Δx)2+(Δy)2(Δx)2=∣AB⏠∣2∣AB∣2⋅[1+(ΔyΔx)2]\begin{aligned} \frac{\Delta s}{\Delta x} &= \frac{|\overgroup{A ...

通常情况下 Python 只能做到在函数体内部判断参数类型进行重载，但我们可以借助 inspect 来实现像一般静态语言那样的重载。为了简化代码，不考虑 positional only 和 keyword only 的参数。