2026-09-19 08:00:00
Notes on CS103: Mathematical Foundations of Computing 🔗link 0.Set Theory and Introduction to Proofs Introduction to Set Theory 势（Cardinality）：反映集合的大小。 定义 $\aleph_0 = |\mathbb{N}|$（可数无穷）。 如果两个集合存在双射，就称这两个集合等势。 自然数集和偶数集是等势的，只需将 n 与 2n 一一对应。 康托定理：$|A| < |\wp(A)|$。 对角线证明法：先假设 $S$ 与它的幂集能一一配对（$s_n$ 配对子集 $A_n$）。构造一个新的子集 $D$，规则是： 对于每一个元素 $s_n$，若 $s_n \not\in A_n$，就把 $s_n$ 放入 $D$。 可以证明 $D$ 一定不在表里。 由于程序的代码一定是字符串，得 $|Programs| \leq |Strings|$。 一个字符串集合可以对应一个判定问题，如给出一个集合 $S = {“a”, “b”, …, “z”}$，它对应一个问题：给一个字符串，判定是不是一个小写字母。所以，由字符串集合定义的问题，和字符串集合本身，是一一对应的。但是，问题绝不仅有判定问题。因此得到 $|Sets of Strings| \leq |Problems|$ 得到：$|Programs| \leq |Strings| \leq |\wp(Strings)| \leq |Problems|$
2023-07-29 08:00:00
最大流 Luogu-P1231 教辅的组成 三倍经验： Luogu-P1402 酒店之王 / Luogu-P2891 [USACO07OPEN] Dining G 一眼丁真建图：S->练习册->书->答案->T 然而是错的。很明显，书有可能被多次匹配，与题意不符。 正确的建图：S->练习册->书（拆点）->答案->T 为什么中间层的书要拆点呢？因为一本书不能被重复选用。我们的目的是保证一本书流出的流量只能是 $1$。所以我们把每个代表书的点拆成两个点，左边的点和练习册连边，右边的点和答案连边；左右对应点之间也要连一条容量为 $1$ 的边。 Luogu-P2764 最小路径覆盖问题 定理：最小路径覆盖数=$|G|$-二分图最大匹配数 首先我们假设现在原图内每个点都是一条路径，此时最少路径数为 $n$。 考虑合并路径，当且仅当两条路径首尾相连的时候可以合并。 将点 $x$ 拆成出点 $x$ 和入点 $x+n$，当我们连接 $u, v$ 时，转化为连接 $u, v+n$。将 $S$ 与所有 $u$ 连边，将所有 $u+n$ 与 $T$ 连边。所有边的容量都为 $1$。 在一开始每个点都是一条独立的路径，每次合并将两条路径合并为一条路径，那么最终路径即为点数减去最大匹配数，这样求得的路径覆盖即为最小路径覆盖。 对于输出路径，用 to 记录下一个节点，tag 标记该节点前面是否还有点。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 ll dfs(int u, int t, ll flow) { if (u == t) return flow; ll ans = 0; vis[u] = 1; for (int &i = cur[u]; ~i; i = e[i].
2023-07-29 08:00:00
最大流 概念 容量：$capacity(e)$ 表示一条有向边 $e(u, v)$ 的最大允许的流量。 流量：$flow(e)$ 表示一条有向边 $e(u, v)$ 总容量中已被占用的流量。 剩余流量（残量）：$w(e) = c(e)-f(e)$，表示当前时刻某条有向边 $e(u, v)$ 总流量中未被占用的部分。 反向边：原图中每一条有向边在残量网络中都有对应的反向边，反向边的容量为 $0$，容量的变化与原边相反；『反向边』的概念是相对的，即一条边的反向边的反向边是它本身。 残量网络：在原图的基础之上，添加每条边对应的反向边，并储存每条边的当前流量。残量网络会在算法进行的过程中被修改。 增广路（augmenting path）：残量网络中从源点到汇点的一条路径，增广路上所有边中最小的剩余容量为增广流量。 增广（augmenting）：在残量网络中寻找一条增广路，并将增广路上所有边的流量加上增广流量的过程。 层次：$level(u)$ 表示节点 $u$ 在层次图中与源点的距离。 层次图：在原残量网络中按照每个节点的层次来分层，只保留相邻两层的节点的图，满载（即流量等于容量）的边不存在于层次图中。 流的三个重要性质： 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即，$f(u,v)\leq c(u,v)$ 斜对称性：每条边的流量与其相反边的流量之和为 0，即 $f(u,v)=-f(v,u)$ 流守恒性：从源点流出的流量等于汇点流入的流量，即 $\forall x\in V-{s,t},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$ 最大流问题：指定合适的流 $f$，以最大化整个网络的流量（即 $\sum_{(s,v)\in E}f(s,v)$）。 Ford-Fulkerson 增广 增广路指一条从 $s$ 到 $t$ 的路径，路径上每条边残余容量都为正。把残余容量为正（$w(u, v) \gt 0$）的边设为可行边，然后搜索寻找增广路。 找到一条增广路后，这条路能够增广的流值由路径上边的最小残留容量 $w(u, v)$（记为 $flow$）决定。将这条路径上每条边的 $w(u, v)$ 减去 $flow$。最后，路径上每条边的反向边残留容量要加上 $flow$。 为什么增广路径上每条边的反向边的残留容量值要加上 $flow$？因为斜对称性，残量网络=容量网络-流量网络，容量网络不变时，流量网络上的边的流量增加 $flow$，反向边流量减去 $flow$，残量网络就会发生相反的改变。从另一个角度来说，这个操作可以理解为「退流」，给了我们一个反悔的机会，让增广路的顺序不受限制。
2023-05-21 08:00:00
CF-559C Gerald and Giant Chess / AtCoder DP-Y Grid 2 给定一个 $H*W$ 的棋盘，棋盘上只有 $N$ 个格子是黑色的，其他格子都是白色的。在棋盘左上角有一个卒，每一步可以向右或者向下移动一格，并且不能移动到黑色格子中。求这个卒从左上角移动到右下角，一共有多少种可能的路线。 $(1 ≤ h, w ≤ 105, 1 ≤ n ≤ 2000)$ $O(hw)$ 的暴力 DP 很好想，但是过不了。 假设没有障碍，从 $(1, 1)$ 到 $(i, j)$ 的方案数是 $C_{i+j-2}^{i-1}$（等于 $C_{i+j-2}^{j-1}$）。可以这么理解：可以用 $D, R$ 来表示一条路径，那么从 $(1, 1)$ 到 $(i, j)$ 的路径中有 $i-1$ 个 $D$ 和 $j-1$ 个 $R$。于是问题转化为从 $i+j-2$ 个位置中选 $i-1$ 个放 $D$ 的方案数。 如果有一个障碍，从正面统计方案数很困难，正难则反，考虑将总的方案数减去经过障碍的方案数。假设障碍的位置是 $(x, y)$，终点是 $(h, w)$，经过障碍的方案数就是 $C_{x+y-2}^{x-1} * C_{h-x+w-y}^{h-x}$（乘法原理）。
2023-05-05 08:00:00
我也不知道这是从哪本书上抠来的？ 整除 定义 1：如果 $a$ 和 $b$ 为整数且 $a \ne 0$，我们说 $a$ 整除 $b$ 是指存在整数 $c$ 使得 $b=ac$。如果 $a$ 整除 $b$，我们还称 $a$ 是 $b$ 的一个因子，且称 $b$ 是 $a$ 的倍数。 如果 $a$ 整除 $b$，则将其记为 $a \mid b$，如果 $a$ 不能整除 $b$，则记其为 $a \nmid b$。 定理 1：如果 $a, b$ 和 $c$ 是整数，且 $a \mid b, b \mid c$，则 $a \mid c$。 定理 2：如果 $a, b, m$ 和 $n$ 为整数，且 $c \mid a, c \mid b$，则 $c \mid (ma+nb)$。
