更佳的阅读体验：2023 国庆集训 Day 6A 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。割点 / 割边在无向图中讨论。删掉这个点 / 边，图变得不连通。Tarjan 求割点随便找个根节点，跑 DFS，记录 DFS 访问的时间戳 $dfn$。对于根节点，我们判断其是否是割点，只需判断是否有大于 $1$ 个子树。考虑非根节点 ：考虑非树边长什么样子：一定是从祖先到子孙。那么假设 $x$ 不是割点，那么子树内的每个点都能到 $x$ 的上面部分。设 $low[x]$ 表示 $x$ 子树内，通过非树边走到的最浅是哪里。如果存在 $x$ 的儿子 $y$ 满足 $low[y] \ge dfn[x]$，那么 $x$ 就是割点。int dfn[N], low[N], cut[N], tmp, num, cnt, rt; void dfs(int x, int fa) { dfn[x] = low[x] = ++num; for (int i = h[x]; i; i = ne[i]) { int y = to[i]; if (y == fa) continue; if (!dfn[y]) { dfs(y, i ^ 1), low[x] = min(low[x], low[y]); if (x != rt && low[y] >= dfn[x]) cut[x] = 1; if (x == rt) tmp++; } else low[x] = min(low[x], dfn[y]); } }缩点参考材料stk[++st] = u; for (int i = point[u]; i != -1; i = edge[i].nxt) { int v = edge[i].v; if (!dfn[v]) { Tarjan(v); low[u] = min (low[u], low[v]); // 因为v在u的子树内，所以low[v]可以用于更新low[u] if (low[v] >= dfn[u]) { // 子树中没有可以连到父亲上面的边 cut[u] = 1; dccn++; dcc[dccn].clear(); dcc[dccn].push_back(u); // u是割点，可能包含在多个点双中，不能弹出 while (true) { int w = stk[st]; dcc[dccn].push_back(w); st--; if (w == v) // 做到子树全部弹出为止，不然v的兄弟也会被弹出 break; } } } }Tarjan 求割边void tarjan(int x, int fa) { low[x] = dfn[x] = ++num; vis[x] = true, st[++top] = x; int cnt = 0; for (int i = h[x]; i; i = ne[i]) { int y = to[i]; if (y == fa && (++cnt) < 2) continue; if (!dfn[y]) tarjan(y, x), low[x] = min(low[x], low[y]); else low[x] = min(low[x], dfn[y]); } if (dfn[x] == low[x] && ++sc) while (z = st[top--]) { col[z] = sc, vis[z] = false; if (z == x) break; } }强连通分量在有向图中，如果两个点 $u$，$v$ 满足同时存在从 $u$ 到 $v$ 和从 $v$ 到 $u$ 的路径，则称两个点强连通。如果有向图任意两个点强连通，则称为强连通图。有向图的极大强连通子图称为强连通分量。注意到强连通关系是传递的，所以有向图可以划分为若干不交的强连通分量。在有向图的 DFS 树中，有 树边、非树边（没用）、返祖边（有用） 和 横叉边（部分有用） 的四种边。DFS 到 x 时，我们用栈维护 $x$ 的每个祖先目前的强连通分量。遍历所有 $x$ 的边 $(x, y)$：如果 $y$ 未被遍历过，则 $dfs(y)$。如果 $y$ 被遍历过，如果 $y$ 在某个祖先的强连通分量中，则形成了环，将若干连通分量合并，否则不做更新。合并操作可以通过记录 $low$ 数组实现。int sta[N], num; bool vis[N]; void tarjan(int x) { low[x] = dfn[x] = ++num; sta[++top] = x, vis[x] = true; for (int i = h[x]; i; i = ne[i]) { int y = to[i]; if (!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); } else if (vis[y]) low[x] = min(low[x], low[y]); } if (dfn[x] == low[x]) { int y; while (y = sta[top--]) { sd[y] = x; vis[y] = false; if (x == y) break; w[x] += w[y]; } } }洛谷 P3469 - [POI2008] BLO-Blockade魔改一下 Tarjan 求割点的过程。得到 $sum - \sum_{low[y] \ge dfn[x]} si[y]$，$ans[x] = (n - sum - 1) \times (sum + 1) + \sum_{low[y] \ge dfn[x]} si[y](n - si[y])$。洛谷 P1407 - [国家集训队] 稳定婚姻婚姻让女方向男方连边，旧情让男方向女方连边。不安全的婚姻说明出现了环，也就是在一个连通分量内。所以跑 Tarjan，一对夫妻在强连通分量里面说明不安全。UOJ 67 - 新年的毒瘤只需满足两个条件：删掉的点不能是割点。删掉这个点以后满足点数等于边数 $+ 1$。洛谷 P4652 - [CEOI2017] One-Way Streets因为保证有解。我们考虑原图中边双里面的边无法确定方向，所以考虑缩边双。缩完以后，现在相当于有一棵树的原问题。可以树上差分，比如从 $x$ 到 $y$，让 $d[x]$ 加 $1$，$d[y]$ 减 $1$，这样边权为正代表向上，边权为负代表向下。CF402E - Strictly Positive Matrix矩阵乘法转化为计算路径的条数。即询问是否存在 $k$ 使得所有 $i$ 到 $j$ 都有长度为 $k$ 的路径。那么需要所有人都在一个强连通分量里面，注意存在某个点有自环，所以可以凑出长度为 $k$ 的路径。洛谷 P3225 - [HNOI2012] 矿场搭建将点双缩点变成一棵树，那么叶子节点一定要建，非叶子节点可以不用建。单独讨论整个图是一个点双的情况。二分图二分图最大匹配：一定存在增广路，扩展所有增广路即可。二分图最小点覆盖：左侧为匹配点开始 DFS，答案为左侧未 DFS 到的点 $+$ 右侧 DFS 到的点。二分图最大独立集：最小点覆盖的补集。洛谷 P1155 - [NOIP2008 提高组] 双栈排序当只有一个栈的时候，怎样是合法的？如果存在 $i < j < k$，$a_k < p_i < p_j$ 不合法。对于两个栈的情况，我们找到所有不合法的 ，这两个人不能放在一起，想到二分图染色。找到字典序最小的合法解。洛谷 P2055 - [ZJOI2009] 假期的宿舍洛谷 P4304 - [TJOI2013] 攻击装置对棋盘黑白染色，有攻击关系建边。那么就是二分图最大独立集 $= n -$ 最大匹配。洛谷 P1129 - [ZJOI2007] 矩阵游戏行和列都建点跑二分图匹配。洛谷 P1263 - [CEOI2002] Royal guards将连续的一段空地而不是一整行建成一个点，类似矩阵游戏的连边。基环树洛谷 P1453 - 城市环路对于树来说，发现就是求最大独立集，设 $f[x][0 / 1]$ 表示 $x$ 点选或不选的最大值。对于环来说，考虑断环为链，相邻两个点一定有一个是不选，分别枚举强制某个点不选做一次链上的 DP 即可。洛谷 P4381 - [IOI2008] Island考虑求一个基环树的直径，先求出树的直径。对于环上的每个点，我们考虑记录 $f[x]$ 表示从 $x$ 开始到其子树内最长路径是多少。断环为链，记录链上的路径前缀和，那么答案就是 $\max(f_i + f_j + s_j - s_i)$，$\max(f_i + f_j + len - (pre_j - pre_j))$，代表走环的两部分。直接扫一遍即可。洛谷 P5049 - [NOIP2018 提高组] 旅行 加强版
更佳的阅读体验：2023 国庆集训 Day 6B 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。矩阵矩阵的运算加 / 减法两个 一样大 的矩阵，对应位置相加 / 减。乘法要求 $n \times m$ 的矩阵与 $m \times k$ 的矩阵相乘，即第一个矩阵的列数等于第二个矩阵的行数。结果是一个 $n \times k$ 的矩阵，即行数等于第一个矩阵的行数，列数等于第二个矩阵的列数。$$ \left[\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}\right] \times \left[\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix}\right] = \left[\begin{matrix} 9 & 12 & 15 \\ 19 & 26 & 33 \end{matrix}\right] $$struct matrix { int n, m; // 矩阵的行数 列数 int a[20][20]; // a[i][j] 代表矩阵第 i 行第 j 列 matrix() { // 构造函数 n = m = 0; memset(a, 0, sizeof(a)); } }; matrix operator*(const matrix &m1, const matrix &m2) { // 计算 m1 * m2, O(n^3) matrix m3; // 结果矩阵 m3.n = m1.n, m3.m = m2.m; for (int i = 1; i <= m3.n; ++i) for (int j = 1; j <= m3.m; ++j) // 计算结果矩阵中第 i 行第 j 列的数 for (int k = 1; k <= m1.m; ++k) m3.a[i][j] += m1.a[i][k] * m2.a[k][j]; return m3; }矩阵快速幂求矩阵 $x$ 的 $y$ 次方。单位矩阵：主对角线为 $1$ 其余为 $0$ 的矩阵 $I = \left[\begin{matrix} 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \end{matrix}\right]$。matrix qpow(const matrix x, int y) { // 计算 x 的 y 次方 matrix ans; ans.n = ans.m = x.n; for (int i = 1; i <= x.n; ++i) ans.a[i][i] = 1; while (y) { if (y & 1) ans = ans * x; x = x * x, y >>= 1; } return ans; }洛谷 P1962 - 斐波那契数列构造一个矩阵 $\left[\begin{matrix} f_i & f_{i - 1} \end{matrix}\right]$​ 和 $\left[\begin{matrix}1 & 1 \\ 1 & 0\end{matrix}\right]$，可得：$$ \left[\begin{matrix} f_1 & f_0 \end{matrix}\right] \times \left[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}\right] ^n = \left[\begin{matrix} f_{n + 1} & f_n \end{matrix}\right] $$使用矩阵快速幂求解，时间复杂度 $O(\log n)$。递推矩阵决定矩阵大小的因素：和前几项有关，例如洛谷 P1939 【模板】矩阵加速（数列）。$$ \left[\begin{matrix} a_i & a_{i - 1} & a_{i - 2} \end{matrix}\right] \times \left[\begin{matrix} \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot \end{matrix}\right] = \left[\begin{matrix} a_{i + 1} & a_i & a_{i - 1} \end{matrix}\right] $$BZOJ #2396. 神奇的矩阵对于 $N \le 10^3$，直接矩阵乘法显然会超时。对于矩阵 $A$，$B$，$C$，直接进行 $A \times B = C$ 会达到 $O(n^3)$。考虑构造一个 $1 \times n$ 的矩阵 $D$，计算 $D \times A \times B = D \times C$，每次乘法都是 $1 \times n$ 的矩阵，时间复杂度 $O(n^2)$。随机一个 $D$，与 $A \times B$ 和 $C$ 相乘并进行比较，显然正确率非常高。逆元用于模意义下的除法。费马小定理：当 $p$ 是质数，如果有 $a$ 满足 $\gcd(a, p) = 1$，则有 $a^{p - 1} \equiv 1 (\mod p)$。对上述同余式两边同时除以 $a$，得到 $a^{p - 2} \equiv a^{-1} (\mod p)$，即模 $p$ 意义下 $a^{p - 2}$ 与 $a^{-1}$ 相同。所以，$a$ 在模 $p$ 意义下的逆元为 $a^{p - 2}$。组合数学$C(n, m)$ 表示从 $n$ 个数中选择 $m$ 个 不同顺序算一种方案 的总方案数。$$ C(n, m) = \frac{n(n - 1)(n - 2) \cdots (n - m + 1)}{m!} = \frac{n!}{m!(n - m)!} $$性质组合数的递推式：$C(n, m) = C(n - 1, m - 1) + C(n - 1, m)$。从以上递推式可以得到杨辉三角，则左对齐的杨辉三角上第 $i$ 行第 $j$ 列的数即为 $C(i, j)$。Example给定三个数 $n$，$m$，$p$，求 $C(n, m) \mod p$。Subtask 1: $n, m \le 1000$递推预处理杨辉三角。int c[N][N]; for (int i = 0; i <= n; ++i) { c[i][0] = 1; for (int j = 1; j <= i; ++j) c[i][j] = c[i - 1][j - 1] + c[i - 1][j] % p; }练习题：洛谷 P2822 [NOIP2016 提高组] 组合数问题。Subtask 2: $n, m \le 10^6$，$p \approx 10^9$，且 $p$ 是质数预处理阶乘以及阶乘的逆元。int fac[N], ifac[N]; // fac[i] 代表 i! % p, ifac[i] 代表 1 / i! % p fac[0] = 1; for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % p; for (int i = 0; i < N; ++i) ifac[i] = qpow(fac[i], p - 2); int C(int n, int m) { // 求 C(n, m) % p, C(n, m) = n! / m! / (n - m)! return 1ll * fac[n] * ifac[m] % p * ifac[n - m] % p; }Subtask 3: $n \le 10^9, m \le 10^3, p \le 10^9$，$p$ 不保证是质数使用公式 $C(n, m) = \frac{n(n - 1)(n - 2) \cdots (n - m + 1)}{m!}$。因为结果一定是整数，则分子一定是分母的倍数。求 GCD。int fenzi[N], fenmu[N]; // 分子，分母 int C(int n, int m) { for (int i = 1; i <= m; ++i) { fenzi[i] = n - i + 1; fenmu[i] = i; } for (int i = 1; i <= m; ++i) for (int j = 1; j <= m; ++j) { int g = __gcd(fenzi[i], fenmu[j]); fenzi[i] /= g, fenmu[j] /= g; } int ans = 1; for (int i = 1; i <= m; ++i) ans = 1ll * ans * fenzi[i] % p; return ans; }概率和期望加法原理与乘法原理加法原理：同阶段互斥； 乘法阶段：不用阶段不互斥。条件概率已知事件 $B$ 发生时事件 $A$ 发生的概率 $P(A|B)$。Example 1假设有 $3$ 张形状相同的卡片，其中一张两面都是黑色，一张两面都是红色，另一张是一面红一面黑，随机取出一张放在桌上，朝上的面为红色，那么另一面是黑色的概率是多少？得到答案 $\frac{1}{3}$。Example 2$n$ 个人按任意顺序一次抓阄，每个人抓完阄后立即打开，当某个人抓到「中」时，整个抓阄过程结束（后面的人就不必抓了）。问：此种抓阄方式是否公平，请说明理由。每个人的概率都是 $\frac{1}{n}$，公平。Example 3在小葱和小泽面前有三瓶药，其中有两瓶是毒药，每个人必须喝一瓶。小葱和小泽各自选了一瓶药，小泽手速比较快，将药喝了下去，然后就挂掉了。小葱想活下去，它是应该喝掉手上的这瓶，还是另外剩下的一瓶呢？无论是否更换手上的药水，小葱挂掉的概率为 $50 \%$，则换与不换答案不变。Example 4小葱想要过河，有两条路：一条路有 $100$ 个石头，每个石头有 $\frac{1}{100}$ 的概率会挂掉。另一条路有 $1000$ 个石头，每个石头有 $\frac{1}{1000}$ 的概率会挂掉。小葱应该走哪边呢？（请勿使用计算器）走第一条路活下来的概率为 $(\frac{99}{100})^{100}$，走第二条路活下来的概率为 $(\frac{999}{1000})^{1000}$。整理并约分后得到 $(\frac{99}{100})^{100} < (\frac{999}{1000})^{1000}$，所以应该走第二条路。Example 5小泽在数轴上的点 $0$ 处。小泽每次有 $r$ 的概率向右走，有 $1 - r$ 的概率向左走，问小泽走到 $-1$ 的概率。令答案为 $p$，得到 $p = (1 - r) + rp^2$，解得 $p = \frac{1 - r}{r}$。思考当 $r < \frac{1}{2}$ 时 $p$ 的值。此时应有 $p = 1$。期望$\sum$ 每一种情况的权值 $\times$ 这种情况的概率。和的期望等于期望的和：$E(X_1 + X_2) = E(X_1) + E(X_2)$。BZOJ #2969. 矩形粉刷令第 $i$ 行第 $j$ 列的格子为 $x_{i, j}$，$x_{i, j} = 0$ 时表示这个格子没有被刷，$x_{i, j} = 1$ 表示这个格子已经被刷。令 $X=被刷格子数量$，得到 $E(X) = E(x_{1,1} + x_{1, 2} + \cdots + E_{n, m})$。令 $p_{i, j}$ 为第 $i$ 行第 $j$ 列的格子被刷过的概率，则 $E(X) = \sum p_{i, j}$。总情况数为 $n^2m^2$，能刷掉 $(i, j)$ 的方案数为 $i(n - i + 1) \cdot j(m - j + 1)$，则只刷一次刷掉 $(i, j)$ 的概率 $q_{i, j} = \frac{i(n - i + 1) \cdot j(m - j + 1)}{n^2m^2}$，一次刷不掉的概率为 $1 - q_{i, j}$，$k$ 次刷不掉的概率为 $(1 - q_{i, j})$。得到 $p_{i, j} = 1 - (1 - q_{i, j})^k$，所以 $E(X) = \sum p_{i, j} = \sum [1 - (\frac{i(n - i + 1) \cdot j(m - j + 1)}{n^2m^2})^k]$。
更佳的阅读体验：2023 国庆集训 Day 5A 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。并查集并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。顾名思义，并查集支持两种操作：合并（Union）：合并两个元素所属集合（合并对应的树）。查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合。并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。并查集无法以较低复杂度实现集合的分离。初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。查询我们需要沿着树向上移动，直至找到根节点。size_t dsu::find(size_t x) { return pa[x] == x ? x : find(pa[x]); }路径压缩size_t dsu::find(size_t x) { return pa[x] == x ? x : find(pa[x]); }合并要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。void dsu::unite(size_t x, size_t y) { pa[find(x)] = find(y); }启发式合并启发式合并 + 路径压缩：$O(m\alpha)$。不使用启发式合并、只使用路径压缩的最坏时间复杂度是 $O(m \log n)$ 。不使用启发式合并、只使用路径压缩，在平均情况下，时间复杂度依然是 $O(m\alpha(m, n))$。如果只使用启发式合并，而不使用路径压缩，时间复杂度为 $O(m \log n)$。由于路径压缩单次合并可能造成大量修改，有时路径压缩并不适合使用。例如，在可持久化并查集、线段树分治 + 并查集中，一般使用只启发式合并的并查集。带权并查集我们还可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。CEOI1999 - Parity Game带权并查集 / 种类并查集。转化为前缀和，每次询问相当于得知 $S[r]$ 和 $S[l - 1]$ 是否是同奇同偶。种类并查集：对于每个位置建立两个点 $i$，$i + n$ 分别代表， 为奇， 为偶。得知两个位置同奇同偶，那么 $i$ 和 $j$ 连，$i + n$ 和 $j + n$ 连，否则 $i$ 和 $j + n$ 连，$j$ 和 $i + n$ 连。一个集合内部的布尔变量相同，当 $i$ 和 $i + n$ 在同一集合时矛盾。带权并查集：相等连一条权值为 $0$ 的边，否则连一条权值为 $1$ 的边，要求两个点的路径异或和要么都为 $1$ （奇偶性不同），要么都为 $0$（奇偶性相同）。实现时维护到达集合代表点的距离即可。NOI Online #1 提高组 - 序列带权并查集与二分图。把每个位置看成一个点。首先对于 $2$ 操作连边。每次操作可以在一个连通块内部任选一个点加一，任选一个点减一。再对于 $1$ 操作连边。如果形成的图是二分图，则可以在保证左部点总和与右部点总和的差不变的情况下任意的加减。如果形成的图不是二分图，则可以在保证总和奇偶性不变的情况下任意的加减。洛谷 P2391 - 白雪皑皑倒序操作，需要支持将区间没有染色的地方染色。并查集：暴力染色，并删除染过的地方。令 $f[i]$ 从 $i$ 开始第一个没有染色的地方。染色后将 $f[i]$ 设置为 $f[i] + 1$，利用并查集维护。洛谷 P1640 - [SCOI2010] 连续攻击游戏建图分析。对于每种装备，将其两种属性连边。对于每个连通块来说，如果是一棵树，那么恰好会有一个属性选不到，那么让连通块的最大值选不到。否则至少是个基环树，所有值都可以选到。最终答案就是选不到的属性的最小值。CF571D - Campus启发式并查集。集合可以想到并查集，但是并查集会破坏合并结构，我们考虑使用启发式合并。如果得到某个位置最后一次清 0 是什么时刻，那么只考虑这个时刻之后的加法操作即可。我们用启发式合并维护信息，第二类集合维护上一次清零的时间，清零就在根结点处打 tag，需要记录连接的时间。然后可以离线下来，变成前缀和相减。加法操作可以记录自己连上来时候父亲的 tag，查询时拿父亲的 tag 减去记录的值即为正确的答案。最小生成树洛谷 P1396 - 营救最小生成树思想。将边从小到大排序，然后 Kruskal 最小生成树连边，这样当 $S$ 和 $T$ 第一次联通时，当前边的权值就是答案了。CF1245D - Shichikuji and Power Grid建图。新建一个虚点，和其相连表示新建电厂，跑最小生成树。洛谷 P8074 - [COCI2009-2010#7] SVEMIR去除冗边。最小生成树，但代价比较特殊。不妨设两个点的距离由 $x$ 决定，代价为 $\lvert x_A - x_B \rvert$，我们发现在数轴上 $x_A$ 和 $x_B$ 必定是相邻的，否则不如把邻居加进来。所以我们只需 $3n$ 条边，只考虑 $x$，$y$，$z$ 相邻权值连边，跑最小生成树即可。洛谷 P8207 - [THUPC2022 初赛] 最小公倍树去除冗边。洛谷 P5994 - [PA2014] Kuglarz思维题。第一步要做前缀和 $S_i$，那么每次询问相当于求 $S_j - S_{i - 1}$ 的奇偶性，我们可以连一条边。也就是求出 $S_j$ 和 $S_{i - 1}$ 的奇偶关系。假设我们得到了最终答案，相当于我们知道了所有 $S_i$ 的奇偶性。而我们知道所有 $S_i$ 的奇偶性后，我们可以通过 $S_i - S_{i - 1}$ 求出第 $i$ 个位置的答案。所以说原问题等价于求出所有 $S_i$ 的奇偶性，因为我们知道 $S_0$ 是偶数，所以就是求最小生成树！洛谷 P1967 - [NOIP2013 提高组] 货车运输经典题。最优情况下一定是走最大生成树，所以相当于询问最大生成树上两点之间的最小边权，我们用倍增维护即可。洛谷 P4180 - [BJWC2010] 严格次小生成树次小生成树一定是将某个非树边代替换上的一条边形成的。那么一定代替最大值或严格次大值，倍增记录即可。CF827D - Best Edge Weight分别考虑树边和非树边。非树边：只需比环上最大的边小即可，倍增维护即可。树边：需要小于所有跨过这个树边的非树边中的最小值，倍增打 tag。
更佳的阅读体验：2023 国庆集训 Day 5B 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。最短路洛谷 P4667 - [BalticOI 2011 Day1] Switch the Lamp On更优的复杂度：$O(NM)$。每个格子看作点。如果当前电线是左上到右下，建边权为 $0$ 的边； 如果当前电线是右上到左下，建边权为 $1$ 的边，表示需要改变。反之亦然。01 最短路，用队列维护。洛谷 P1462 - 通往奥格瑞玛的道路最大值最小？二分！保留二分值以下的边，跑最短路，检查是否能活着到达 $n$ 号点。洛谷 P1144 - 最短路计数洛谷 P1119 - 灾后重建Floyd 理解。洛谷 P4822 - [BJWC2012] 冻结分层图。分层图，建 $k + 1$ 层点跑最短路。另一视角：动态规划。洛谷 P9402 - [POI2020-2021R3] Droga do domu分层图。按照 $k$ 分层，设 $f[k][i]$ 表示换乘了 $k$ 次，到达第 $i$ 个点最早什么时间到。如何转移？因为公交车线路经过哪些点是有顺序的，我们枚举每条线路，从前向后走即可。洛谷 P2371 - [国家集训队] 墨墨的等式同余最短路。考虑 $b \mod a_1 = \sum_{i = 2}^n a_i x_i \mod a_1$。以 $a_1$ 为中心视角，如果 $b$ 能拼出来，那么 $b + a_1$，$b + 2a_1$，$b + ka_1$ 都能拼出来。也就是 $\mod a_1$ 同余的从一个开头开始，后面都能拼了。我们考虑用 DP / 最短路求出这个开头是多少。设 $f[i]$ 表示用 $a_2, \cdots, a_n$ 拼出最小 $\mod a_1 = i$ 的数是多少，转移，$f[i] = \min_{j = 2}^n f[i - a_j \mod a_1]$。AT_arc084_b - [ABC077D] Small Multiple如同余最短路。洛谷 P5304 - [GXOI/GZOI2019] 旅行者随机分组或二进制分组。分成两组 ，求出从 $A$ 某个点到 $B$ 某个点的最短路。新建超级原点和超级终点即可。差分约束洛谷 P3385 - 【模板】负环负环。洛谷 P5590 - 赛车游戏差分约束。洛谷 P3530 - [POI2012] FES-Festival$A$ 恰好比 $B$ 快 $1$ 秒，可以用两个不等式来约束，$A \le B - 1$，$A \ge B - 1$。我们发现所有关系都可以用不等式来约束，所以考虑差分约束。对于强连通分量，任意两个点都有约束，我们找到最短路最大的两个点 $+ 1$ 即为此连通分量的答案，不同联通分量的答案不影响。连通分量内部，由于此题两点距离是 $1$，所以如果存在一个最短路，那么最短路的所有值都可以取到。连通分量之间由于只有单向关系，可以令一个无限小，一个无限大，使得不同连通分量处于不同的值域。拓扑排序洛谷 P1983 - [NOIP2013 普及组] 车站分级洛谷 P5603 - 小 C 与桌游洛谷 P3243 - [HNOI2015] 菜肴制作洛谷 P6286 - [COCI2016-2017#1] Cezar比较两个字符串字典序大小，我们只需考虑第一个不一样的位置即可。假设第一个不一样的字符分别为 $s_1$，$s_2$，并且 $s_1$ 所在字符串字典序更小，那么一定有 $a < b$，连边跑拓扑序即可。洛谷 P3243 - [HNOI2015] 菜肴制作倒着求字典序最大的拓扑序即可。练习[P4079 [SDOI2016] 齿轮](https://www.luogu.com.cn/problem/P4079)[P4092 [HEOI2016/TJOI2016] 树](https://www.luogu.com.cn/problem/P4092)[P1525 [NOIP2010 提高组] 关押罪犯](https://www.luogu.com.cn/problem/P1525)[P3207 [HNOI2010] 物品调度](https://www.luogu.com.cn/problem/P3207)[P4568 [JLOI2011] 飞行路线](https://www.luogu.com.cn/problem/P4568)P3403 跳楼机[[ABC077D] Small Multiple](https://www.luogu.com.cn/problem/AT_arc084_b)[P3275 [SCOI2011] 糖果](https://www.luogu.com.cn/problem/P3275)[P7113 [NOIP2020] 排水系统](https://www.luogu.com.cn/problem/P7113)[P7860 [COCI2015-2016#2] ARTUR](https://www.luogu.com.cn/problem/P7860)[P6560 [SBCOI2020] 时光的流逝](https://www.luogu.com.cn/problem/P6560)[P7831 [CCO2021] Travelling Merchant](https://www.luogu.com.cn/problem/P7831)
更佳的阅读体验：2023 国庆集训 Day 3B 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。树形 DP依照树的性质进行的 DP。把树分为许多子结构，通过子结构包含的信息来设计状态，通常是由子结点向父节点转移。以下所有关于树形 DP 的内容，规定 $x$ 为当前结点，$y$ 为其子节点。求树上两两距离和求 $dis[i][j]$。统计每条边的贡献：$size[x] \times (n - size[x])$。洛谷 P3047 - Nearby Cows G令 $f[x][i]$ 为 $x$ 子树内，和 $x$ 距离 $\le i$ 的点的点权和，$f[x][i] = c_x + \sum f[y][i - 1]$。求 $ans_x$ 时，令 $fa[x][i]$ 为 $x$ 的第 $i$ 级祖先，则 $ans_x = \sum f[fa[x][i]][k - i] - f[fa[x][i - 1]][k - i - 1]$。复杂度为 $O(nk)$。洛谷 P2014 - 选课把 $a$ 是 $b$ 的先修课程视为 $a$ 是 $b$ 的父亲，那么会形成一个森林。设 $f[x][i]$ 为 $x$ 子树中修读 $i$ 门课的最大学分数。依次枚举 $x$ 的每个儿子，设当前儿子为 $y$，利用老 $f[x]$ 与 $f[y]$ 合并出新 $f[x]$。老 $f[x]$ 意为不含 $y$ 子树的信息（也就是只考虑 $y$ 之前的所有儿子的子树）。那么 $f_新[x][i] = \max(f_老[x][j] + f[y][i - j])$。注意由于根节点 $x$ 必须选，那么要求 $j > 0$。复杂度为 $O(nm^2)$。经典的树形背包问题，利用 DFS 序可以优化为 $O(nm)$。求树的直径类似于上一题的合并，记录 $x$ 的当前深度。如果要对直径计数，额外记录数量。洛谷 P3174 - 毛毛虫答案为 $\max (\sum (deg[i] - 1) + 2)$，树形 DP 求最长链。或使用两遍 DFS 求直径。树上最大独立集 / 最小点覆盖最大独立集：选择尽可能多的点，但是父亲和儿子不能同时选择； 最小点覆盖：选择尽可能少的点，但是父亲和儿子至少选一个。令 $f[x][0 / 1]$ 表示在结点 $x$ 选 / 不选的情况下，$x$ 子树内的最大独立集点数； 令 $g[x][0 / 1]$ 表示在结点 $x$ 选 / 不选的情况下，$x$ 子树内的最小点覆盖点数。令根节点为 $r$，则答案为 $\max (f[r][0], f[r][1])$，$\min (g[r][0], g[r][1])$。洛谷 P2899 - Cell Phone Network G令 $f[x][0 / 1 / 2]$ 表示 $x$ 子树内的最小信号塔数，其中 $x$ 被儿子 / 自己 / 父亲覆盖。洛谷 P4084 - Barn Painting G令 $f[x][0 / 1 / 2]$ 表示 $x$ 染成三种颜色的子树内方案数。树上拓扑序计数给定一棵外向树（每条边的方向是从父亲到儿子），求其拓扑序个数。$n \le 10^5$。多重集合排列数公式： $\frac{(\sum a_i)!}{\prod a_i!}$，$a_i$ 为集合中第 $i$ 个元素的数量。令 $f[i]$ 表示 $i$ 的子树的拓扑序个数。$i$ 子树内首先第一位必须是 $i$，然后剩下的 $size[i] - 1$ 个位置需要分配给其儿子的子树。若 $i$ 有 $k$ 个儿子 $j_1, j_2, \cdots, j_k$，则分配位置的方案数为 $\binom{size[i] - 1}{size[j_1]} \binom{size[i] - 1 - size[j_1]}{size[j_2]} \cdots \binom{size[i] - 1 - size[j_1] - \cdots - size[j_{k - 1}]}{size[j_k]} = \frac{(size[i] - 1)!}{\prod size[j]!}$。然后再乘上 $f[j_1]f[j_2] \cdots f[j_k]$。树上问题在树上选出 $m$ 条边互不相交的链，使得他们的长度和最大。$n \le 10^5$，$m \le 10$。令 $f[x][i][0 / 1]$ 表示 $x$ 的子树选择 $i$ 条链，是 / 否有一条从儿子伸到 $x$ 的半链的最大长度和。转移时枚举儿子 $y$：$f[x][j][0] + f[y][i - j][0] \to f'[x][i][0]$，$f[x][j][1] + f[y][i - j][0] \to f'[x][i][1]$（树形背包）。$f[x][j][1] + f[y][i - j - 1][1] + dis(x, y) \to f'[x][i][0]$（半链合并）； $f[x][j][0] + f[y][i - j][1] + dis(x, y) \to f'[x][i][1]$（半链伸上来）。状压 DP将当前需要用到的状态记录并压缩。例如一般的序列 DP 可能只需要记录 $i$ 表示 $1 \sim i$，而状压 DP 可能需要记录 $1 \sim i$ 中具体哪些位置在状态中。洛谷 P1171 - 售货员的难题设 $f[S][i]$ 表示从 $1 \to i$ 一共经过了村庄集合 $S$ 的最短路。$f[S][i] = \min(f[S - i][j] + dis[j, i])$。复杂度为 $O(n^2 2^n)$。这与搜索不同之处在于，状压 DP 只关注了去过村庄的集合，而搜索关注访问它们的顺序。在 TSP 问题中，知道访问顺序是没用的。洛谷 P1559 - 运动员最佳匹配问题•与旅行商问题一样，在后面的运动员进行匹配时，我们只关心有哪些运动员已经匹配了，而不关心他们具体是怎么匹配的。这就是状压 DP 相较于普通搜索优化的方式。设 $f[i][S]$ 表示考虑男 $1 \sim i$ 号运动员，已经匹配的女运动员集合为 $S$ 的最大竞赛优势和。考虑第 $i$ 号男运动员与哪位女运动员匹配了，那么有 $f[i][S] = \max⁡(\sum f[i - 1][S - j] + P_{i, j} Q_{j, i})$ 。洛谷 P1896 - 互不侵犯按行转移。设 $f[i][j][S]$ 表示前 $i$ 行，共 $j$ 个国王，第 $i$ 行的状态为 $S$ 的方案数。洛谷 P2704 - 炮兵阵地直接转移会导致产生 $2^{20}$ 的状态数，需要预处理。按行转移，记录这一行以及上一行的状态。洛谷 P2157 - 学校食堂做菜时间的计算式是无关紧要的。由于每个人只允许最多 $7$ 个人插队，那么只需要状压当前结尾 $7$ 个人是否已经取餐。设 $f[i][j][S]$ 表示考虑 $1 \sim i$ 的人，最后一个取餐的是 $j$ ，结尾 $7$ 个人取餐的状态为 $S$ 的最小总时间。枚举下一个取餐的是谁进行转移。洛谷 P3226 - 集合选数把一个数的 $2$ 倍排在它下面，$3$ 倍排在它右面，会形成一个网格图，状压每一行选择哪些数。$\mod 6 = 1, \mod 6 = 5$ 的数字会位于左上角。两个相邻的点不选即可。
更佳的阅读体验：2023 国庆集训 Day 4A 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。状压 DP洛谷 P4363 - 一双木棋只需要将当前局面下所放棋子的轮廓线压入状态即可，DP 初值为 $f[整个棋盘] = 0$。状压当前的轮廓线，依据这一步该谁下进行 min / max 搜索。洛谷 P5369 - 最大前缀和统计每个子集作为最大前缀和的次数。如果某个前缀和是最大前缀和，那么这个前缀的所有后缀和都 $> 0$，后面的所有前缀和都 $\le 0$。设 $f[S]$ 为将 $S$ 排列成所有后缀 $> 0$ 的方案数，$g[S]$ 为将 $S$ 排列成所有前缀 $\le 0$ 的方案数。答案即为 $\sum sum[S]f[S]g[U-S]$，$U$ 为全集。洛谷 P5492 - 随机算法求图上最大独立集。设 $f[S]$ 为 $S$ 内随机一个排列的正确方案数。枚举 $S$ 排列的第一个元素 $x$，加入 $x$ 会导致删除 $x$ 及与其相邻的点集 $c_x$。那么如果 $max⁡[S]=max⁡[S-c_x ]+1$，就令 $f[S]$ 加上 $f[S-c_x]$ 。int ctz[1 << N]; long long f[1 << N], g[1 << N]; long long c[N]; const long long p = 998244353; cin >> n >> m; for (int i = 0; i < m; i++) { cin >> x >> y; c[x] |= 1 << y; c[y] |= 1 << x; } for (int i = 0; i < n; i++) { ctz[1 << i] = i; } for (int S = 1; S < 1 << n; S++) { int x = ctz[S & -S]; g[S] = max(g[S - (1 << x)], g[S - (1 << x) - (c[x] & S)] + 1); } f[0] = 1; for (int S = 1; S < 1 << n; S++) { for (int x = 0; x < n; x++) { if (~S >> x & 1) <=> if (!(S >> x & 1)) continue; if (g[S - (1 << x) - (c[x] & S)] + 1 < g[S]) continue; f[S] = (f[S] + f[S - (1 << x) - (c[x] & S)]) % p; } } cout << f[(1 << n) - 1] /n! << endl; 图上拓扑序计数给定一张 DAG，求其合法拓扑序个数。$n \le 20$，$m \le \frac{n(n - 1)}{2}$。设 $f(S)$ 表示 $S$ 诱导子图的拓扑序个数。转移时，枚举 $S$ 中拓扑序最靠前的节点 $i$：$f(S) = \sum_{i \in S, ind_i = 0}f(S-\{i\})$ 。其中 $ind_i=0$ 表示 $i$ 在 $S$ 中没有入度（而非整个图中）。// topo count long long f[1 << N]; bool valid(int x, int s) { // s 没有连向 x 的边 } for (int s = 1; s < 1 << n; ++s) { for (int x = 0; x < n; ++x) { if (~s >> x & 1) continue; if (valid(x, s)) f[s] += f[s - (1 << x)]; } }边子集拓扑序计数给定一张有向图（不保证是 DAG）。设其边集为 $E$ 。对于 $T \subseteq E$ 定义 $f(T)$ 为保留 $T$ 时整张图的拓扑序数量，求 $∑_{T \subseteq E}f(T)$。$n \le 20$，$m \le n(n-1) $。设 $g(S)$ 表示 $S$ 诱导子图的答案，我们输出 $g(U)$。与其统计每个边集 $T$ 的拓扑序方案数，不如统计每种拓扑序能在多少种 $T$ 下合法。转移时仍然枚举 $S$ 中拓扑序最靠前的节点 $i$ 。要想让 $i$ 最靠前合法，就需要让 $i$ 在 $S$ 内的 $ind=0$。换句话说，不能保留从 $S-\{i\}$ 连向 $i$ 的边，而 $i$ 连向 $S-\{i\}$ 的边可以任意保留。所以 $g(S) = \sum_{i \in S} f(S-\{i\}) 2^{cnt_{i,S-\{i\}}}$，其中 $cnt_{i,S-{i}}$ 表示 $i$ 连向 $S-\{i\}$ 的边数。// topo count with edge subset long long count[N][1 << N]; cin >> n >> m; for (int i = 0; i < m; ++i) { cin >> x >> y; for (int s = 1; s < 1 << n; ++s) if (s >> y & 1) ++count[x][s]; } for (int s = 1; s < 1 << n; ++s) for (int x = 0; x < n; ++x) { if (~s >> x & 1) continue; f[s] += f[s - (1 << x)] << count[x][s - (1 << x)]; }洛谷 P2831 - 愤怒的小鸟每个优的抛物线至少经过两只猪。用 $\begin{cases} y_1 = ax_1^2 + bx_1 \\ y_2 = ax_2^2 + bx_2 \end{cases}$ 可解出一组 $(a, b)$。共有 $O(n^2)$ 组。预处理出每两只猪 $(i, j)$ 形成的抛物线能消灭哪些猪 $c[i][j]$ 。设 $f[S]$ 为消灭 $S$ 集合猪最少需要多少只小鸟。枚举第一条抛物线，则 $f[S] = \min⁡(f[S-c[i][j]]+1)$。固定 $i$ 为 $S$ 中的最小元，则只需枚举 $j$ 即可。复杂度为 $O(n2^n)$。洛谷 P3959 - 宝藏对于 $v$ 相等的部分分，可以使用贪心求解。状态中需记录当前层数。设 $f[x][i][S]$ 为 $x$ 的子树编号集合为 $S$，$x$ 在第 $i$ 层的最小子树代价。得到转移方程 $f[x][i][S] = \min⁡(f[x][i][T]+f[y][i+1][S-T]+dis(x,y) \times i)$。取答案时枚举每个点作为起始点。
更佳的阅读体验：2023 国庆集训 Day 4B 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。单调队列优化 DP洛谷 P1886 - 单调队列int a[N]; deque<int> q; // 存每个数的下标 for (int i = 1; i <= n; ++i) { while (!q.empty() && q.front() <= i - k) q.pop_front(); while (!q.empty() && a[q.back()] <= a[i]) q.pop_back(); q.push_back(i); cout << a[q.front()] << '\n'; }洛谷 P2216 - 理想的正方形洛谷 P2219 - 修筑绿化带求出每一块花园中，花坛应该放在哪里。如果花园的右下角为 $(x, y)$，那么花坛的右下角就应位于 $(x - a + c + 1, y - b + d + 1) \sim (x - 1, y - 1)$ 这个矩形内。求出这个矩形内最小的 $sum$。求最大全 0 正方形给定一个 0 / 1 矩阵，求出最大的全为 0 的子正方形，求不带 $\log$ 的做法。带 $\log$ 的做法：枚举每个点作为左上角，二分正方形边长。令 $f[i][j]$ 表示矩形 $(i, j)$ 位置往下延伸 $0$ 的个数，得到转移方程 $f[i][j] = \begin{cases} 0, a_{i, j} = 1 \\ f[i + 1][j] + 1, a_{i, j} = 0 \end{cases}$。枚举正方形的上边界 $u$，依次从 $1 \sim n$ 枚举正方形的右边界。维护一个左边界的指针，并用单调队列维护左右边界之中的 $f$ 值，需要时刻保证 $r - l + 1 \le \min ⁡f$ 。复杂度为 $O(n^2 )$。带修版本：洛谷 P4259 - 寻找车位洛谷 P2254 - 瑰丽华尔兹设 $f[t][i][j]$ 为 $t$ 时刻到达 $(i, j)$ 的最长路程。假如 $t$ 时刻钢琴是往上方滑动，那么 $f[t][i][j] = \max (f[t - 1][i + 1][j] + 1, f[t - 1][i][j])$。往其他方向同理。复杂度为 $O(nmT)$。由于时间可以被分为 $K$ 段，每段滑动方向相同，则可以修改状态，令 $f[k][i][j]$ 为第 $k$ 个时间段结束后到达 $(i, j)$ 的最长路程。$f[k][i][j] = \max {f[k - 1][i + s][j] + s), 0 \le s \le t_k}$。使用单调队列优化。复杂度 $O(nmK)$。// 不考虑障碍 且只考虑向上的转移 for (int k = 1; k <= K; ++k) { int t_k; for (int j = 1; j <= m; ++j) { deque<int> q; int g[]; for (int i = 1; i <= n; ++i) g[i] = f[k - 1][i][j] + i; for (int i = n; i; --i) { while (!q.empty() && q.front() > i + t_k) q.pop_front(); while (!q.empty() && g[q.back()] <= g[i]) q.pop_back() q.push_back(i); f[k][i][j] = g[q.front()] - i; } } }洛谷 P4381 - Island求若干个基环树的直径之和。对于一个基环树，找到它的环，求出环上每个节点 $i$ 环外延伸的最长距离 $d_i$。将长为 $m$ 的环破为长为 $2m$ 的链。如果从节点 $i$ 外面走到节点 $j$ 外面，则距离为 $j - i + d_i + d_j$，同时要求 $i < j < i + n$。使用单调队列优化求解。复杂度为 $O(n)$。单调队列优化多重背包一共有 $c_i$ 个 $i$ 号物品，有 $w_i$ 的价值和 $v_i$ 的体积。洛谷 P5665 - 划分贪心地使最后一段的和尽可能小。不严谨证明：如果最后一段 $[l, r]$ 的和没到达下界，那么可以不断地把 $a_l$ 分给前一段。由于 $s_i < s_{i+1}$，分给前一段的贡献是 $2a_l s_i$，分给后一段的贡献是 $2a_l s_{i+1}$，则分给前一段更优，同时分给前一段也有利于后面的分段。所以设 $f[r]$ 为 $\max⁡ {l-1: 最后一段分成 [l, r] 可行}$，应有 $sum_r - sum_{l-1} \ge sum_{l-1}-sum_{f[l-1]}$，即 $sum_r \ge 2sum_{l-1} - sum_{f[l-1]}$，双指针即可。复杂度为 $O(n)$。计数 DP洛谷 P5824 - 十二重计数法洛谷 P3702 - 序列计数用总方案数去掉不含质数的方案数。分别用 DP 求解，设 $f[i][j]$ 为 $i$ 个数字，和 $\mod p = j$ 的方案数，矩阵快速幂加速。复杂度 $O(p^3 \log⁡ n )$。洛谷 P3773 - 吉夫特由 Lucas 定理可知 $C_n^m$ 是奇数 $↔(n\&m)=m$。设 $f[T]$ 表示结尾值为 $S$ 的序列个数，转移时枚举子集 $T$，如果 $pos[S] < pos[T]$ 则令 $f[T]$ 加上 $f[S]$。复杂度为 $O(3^w)$。int a[N], pos[N]; cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; pos[a[i]] = i; } for (int s = VALUE_MAX; s; --s) { ++f[s]; for (int t = (s - 1) & s; t; --t) if (pos[s] < pos[t]) f[t] += f[s]; ans += f[s] - 1; }洛谷 P5664 - Emiya 家今天的饭对「每种食材最多在一半菜中」进行容斥。用总的方案数减去某种食材过多的方案数，不会有两种食材同时过多。总方案数易求。枚举过多的食材种类 $t$，设 $f[i][j][k]$ 表示前 $i$ 种烹饪方法，一共做了 $j$ 个菜，其中 $k$ 个使用 $t$ 的方案数。转移时枚举第 $i + 1$ 种烹饪方法是否选用，选用时是否使用 $t$，最后要求 $k > \frac{j}{2}$ 。只需记录 $2k - j$ 的值即可，最后要求此值 $> 0$。复杂度为 $O(n^2 m)$。
更佳的阅读体验：2023 国庆集训 Day 2B 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。搜索NOIP2009 提高组 - 靶形数独可行性剪枝：每次最先搜索可能性最少的点。最优化剪枝：剩下的数最优情况下也不超过全局最优解的剪枝。Example 2有 $q$ 次询问，每次询问一个数 $x$，询问 $x$ 每次除以一个约数直到最后变为 $1$ 有多少种方式，比如 $x = 6$，有$(6 \to 1)$、$(6 \to 3 \to 1)$、$(6 \to 2 \to 1)$ 三种。$x \le 10^{15}$，$q \le 10^4$。对 $x$ 做质因数分解可以使用 $\texttt{Pollard-Rho}$ 算法，期望复杂度为 $O(n^{0.25})$。假设得到了 $x = a_1^{p_1}a_2^{p_2}a_3^{p_3}\cdots a_k^{p_k}$，因此只有 $(p_1, p_2, p_3, \cdots, p_k)$ 的无序元组有意义。这样本质不同的元组数量的一个粗略上限是考虑 $2^{50} \sim 10^{15}$，而 $50$ 的拆分数只有 $2 \times 10^5$ 级别，事实上会少很多。直接暴搜出所有可能的元组组合并排列组合一下计算答案即可。SDOI2015 - 排序首先操作的顺序是无关紧要的，所以我们只需要关心每个操作做没做。我们从小到大 DFS，对于第 $i$ 次操作我们将序列分成 $2^{n-i}$ 段，每段长度 $2^i$。我们找到序列中不是连续递增的段，如果这样的段超过 $2$ 个则不行。如果没有这样的段，就不需要执行这个操作。如果有一个这样的段，判断将这个段的前半部分和后半部分交换后是否连续递增，如果是就交换然后继续 DFS。如果有两个这样的段，判断四种交换情况然后 DFS。二分最大平均子段和给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ 和 $k$，求一个长度大于 $k$ 的区间 $[l, r]$ 使得 $\frac{a_l+\cdots+a_r}{r - l + 1}$ 最大。$n \le 10^5$，输出小数，精度 $10^{-6}$。考虑二分答案 $p$，然后让 $b_i = a_i - p$，只需要看 $b_i$ 构成的序列是否有大于 $0$ 的子段，就可以知道 $a_i$ 序列有没有平均值大于 $p$ 的子段。看 $b_i$ 构成的序列是否有大于 $0$ 的子段可以直接找 $b$ 的最大子段和。LOJ 2776 - 蠕虫之忧Subtask 1二分、三分次数都不够，需要使用黄金分割比分。因为黄金分割比位置在下一层二分处还是该位置。Subtask 2复制一维二分到二维，每次询问中线上最大值点，看看他左右两侧哪一侧增高就去哪边，不过注意可以每次二分较短的一维。同时如果之前查询到的全局最大值比当前线上最大值大，则向全局最大值位置继续二分。Subtask 3注意到 $Q$ 很大，可以使用乱搞随机做法。先用 $\frac{q}{2}$ 次随机询问，问一个最大的点，然后用这个点爬山。期望到山顶的路径长度其实很短。Example 3你在玩一个游戏，游戏中的一个关卡是这样的：有一张 $n$ 个节点和 $m$ 条边的有向图，每条边有一个长度，你的角色一开始在 $1$ 号点移动速度为 $1$ 单位长度每秒，每次到达一个点会带权选择一个随机的出边走出去，在边上移动的时候会消耗对应长度的时间。你的目的是在 $L$ 的时间内到达 $n$ 号点，你可以选择在任意时间重开这一关。求在现实世界过关所需要的最小期望时间，输出实数。$n \le 100$，$m \le 200$，其他所有数在 $10^9$ 以内。二分答案 $T$，在游戏中加入一个虚拟按钮，这个按钮的功能是立刻以T的时间通关。用动态规划算出人物在每一个点的期望通关时间和为了达到这个通关时间的决策（继续走、重开还是按按钮），如果最后我们发现在 $1$ 号点按按钮是最优的则实际通关最小期望时间 $\ge T$,否则 $< T$。分治Example 1给定一个排列，随机做 $k$ 次交换两个数，求最后期望逆序对数。$n \le 5 \times 10^5$，$k \le 10^9$。$k=0$ 的时候就是朴素的逆序对问题，需要分治。考虑直接在 $k \ne 0$ 的时候也硬上分治。对于 $(l, r)$ 节点，我们只统计 $k$ 轮过后期望 $(l, mid)$ 与 $(mid + 1, r)$ 之间的贡献。于是我们的第二个状态变成了 $f[k][0 / 1 / 2][0 / 1 / 2]$，表示第一个数在区间左 / 区间右 / 区间外，第二个在区间左 / 区间右 / 区间外，过 $k$ 轮他们产生贡献的概率。这个 DP 可以用矩阵快速幂加速计算，同时只跟区间长度有关，注意到分治只会产生 $O(\log n)$ 种不同长度的区间，所以矩阵快速幂不在瓶颈上。Example 2：随机点分治给定一棵树 $T$，每次并非选重心而是随机选择一个点进行分治，求期望复杂度。$n \le 10^5$。本题考查了分治过程，考虑一下发现两个距离为 $l$ 的点 $u$，$v$ 发生贡献的情况是 $u$ 到 $v$ 的链上第一个作为分治点的点是 $u$ 或者 $v$，也就是说贡献只和 $l$ 有关 $\frac{2}{l}$。然后相当于统计一颗树每一种长度的链有多少个。点分治 + FFT 即可。点分治：ZJOI2016 - 旅行者考虑将所有询问放在一起分治，从 $n\times m$ 的网格图划一道中线，求出两侧的每一个点到中线的距离，然后如果一个询问起点终点跨过中线就在这一层解决，用两测每一个点到中线的距离求解即可。剩余在同侧的询问递归下去即可。CDQ 分治一类给定一个序列，前面的项/修改对后面有影响但独立，求每一个前缀的影响和。计算 $[1, mid]$。计算 $[1,mid]$ 对 $[mid + 1, r]$ 的贡献。计算 $[mid+1,r]$。贪心Example 1有 $n$ 个怪物，每个怪物 $a_i$ 和 $b_i$，当你打一个怪物的时候会先减少 $a_i$ 血再加 $b_i$ 血，中途血量不能小于 $0$，请问最少初始需要多少血才能打赢所有怪物。$n \le 10^5$。首先考虑 $a_i \le b_i$ 的怪物，即会帮你加血的，显然要先打。显然是先打 $a_i$ 小的。比较困难的是 $a_i \ge b_i$ 的怪物，考虑简单的 $n = 2$的情况，有 $(a_1,b_1)$，$(a_2,b_2)$，先打 $1$ 对血量 $x$ 的限制是 $x \ge \max(a_1, a_1+a_2-b_1)$，先打 $2$ 是 $x \ge \max(a_2,a_1+a_2-b_2)$。可以证明 $\max(a_2,a_1+a_2-b_2)$ 和 $\max(a_1,a_1+a_2-b_1)$ 比大小只和 $b_1$ 与 $b_2$ 大小有关。所以一定先打 $b_i$ 最大的。对于 $n$ 任意的情况我们可以考虑，对于任意方案，我们都可以交换其中两个 $i < j$ 且 $b_i<b_j$ 的怪物使得答案变不劣，所以对任意 $n$ 也成立。IOI 2019 - 排列鞋子因为存在同颜色的多个鞋子，所以我们首先先将鞋子对应关系找出，可以发现对于某种颜色的左脚鞋所在位置 $l_1 < l_2 < \cdots < l_k$ 和与之对应的右脚鞋的位置 $r_1 < r_2 < \cdots < r_k$ 则配对方法一定是 $l_i$ 配 $r_i$ ，即对应匹配。考虑一种可能的答案下界，发现对于一对鞋的位置 $u$、$v$，需要的次数至少为 $v-u-1$，如果右脚在左边则还需要再来一次交换左右脚。考虑两组鞋子的位置 $u_1 < v_1$ 和 $u_2 < v_2$，如果区间 $[u_1, v_1]$ 和区间 $[u_2, v_2]$ 有交则可能将交换次数减少一次，因为最多有一次交换使得两组鞋子都向目的地前进了一步。所以若配对鞋子位罝为 $(u_1, v_1)$，$(u_2, v_2)$，$\cdots$，$(u_n，v_n)$，其中 $u_i < v_i$，则答案最小可能就是每一个鞋子自己的匹配长度相交的区间个数。事实上，这个下界就是答案。相交个数可以将 $u_i$ 从小到大排序后用树状数组求出所有 $u_j<u_i$ 且 $u_i<v_j<v_i$ 的个数（单点修改，前缀查询）。正确性证明如果要使得答案到达答案下界，则需要让每个相交的区间都产生贡献且每个鞋子都不向反方向走，一种可行的方法是考虑与第 $1$ 个位置配对的鞋子的位置 $p$，先将 $p$ 一路向左跟 $1$ 位置匹配，然后这两个鞋子已经就与后面的无关了。直接递归地将第 $3$ 个位置视为第 $1$ 个位置继续做这样的操作，显然在这样的情况下每组配对的鞋子都不会绕远，且每个相交的区间都会产生贡献。快速幂实现幂运算。求逆元。矩阵快速幂实现、线性递推。Floyd 矩阵快速幂，图论里的路径相关问题。NOI2020 - 美食家使用 Floyd 矩阵，$A_{i, j}$ 表示 $i$ 到 $j$ 只经过 $1$ 条边的最短路，$A_{i, j}^k$ 表示经过恰好 $k$ 条边的最短路。$C_{i, j} = \min_k(A_{i, k}, B_{k, j})$。先预处理出 $A$ 的 $2$ 的倍数次幂，询问时二进制分解，访问答案后相乘。时间复杂度 $O(\log^T n^3 + k \log Fn^2)$。首先考虑没有特殊事件的情况。由于每条边很短（$w_i \le 5$）我们可以把每条边拆点，这样就会得到一个 $n \times 5$ 个点的无权有向图，然后使用 Floyd 矩阵乘法快速幂计算 $f[t][i][j]$ 表示用 $t$ 天从 $i$ 走到 $j$ 的最大愉悦值。如果有特殊事件，值假设第一次特殊事件在 $t1$ 天，那么维护一个向量 $g$，$g_i$ 表示花 $t_1$天从 $1$ 走到 $i$ 号点的最大愉悦。$g=f^{t1} \times (0, \infin, \infin \cdots \infin)^T$。然后令 $g_{x_i}$加上 $y_i$，代表特殊事件，然后再继续考虑下一个特殊事件，每次用 $f$ 转移。但是每次都算 $f^t$太慢了，所以我们预处理出 $f,f^2,f^4,f^8\cdots$ 然后每次要算 $f^t \times g$ 的时候利用 $t$ 的二进制分解一个一个把对应的 $f^{2^q}$ 乘到 $g$ 上，这样避免了矩阵乘矩阵。二维 RMQExample 1给定一个 $n \times m$ 的矩阵和 $q$ 次询问，每次询问一个子矩阵的最小值。$n, m \le 300$，$q \le 10^7$。对于 RMQ 问题，考虑 ST 表，本题适用二维 ST 表。和一维一样，令 $f_{i,j,k,l}$ 表示子矩阵 $[i, i + 2^k) \times [j,j + 2^l)$ 的最小值。$f_{i, j, k, l} = \min_{x \in [i, i + 2^k],y \in [j, j + 2^l]} a_{x, y}$。注意空间复杂度 $O(nm \log n \log m)$，如果卡空间可以选择一维线段树，另一维 RMQ。LCATarjan 算法先把 LCA 的询问记录下来，在树上做 DFS，将已访问的点连到一个并查集内。对于已访问的点，表明 LCA 一定在递归调用栈内，返回并查集的父亲；对于未访问的点，跳过，直到访问到该点。#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; struct edge { int to, nxt; } e[N << 1]; int n, m, id, h[N], fa[N], ans[N]; vector<pair<int, int> > q[N]; bool vis[N]; void add(int u, int v) { e[++id] = (edge){v, h[u]}; h[u] = id; } int getroot(int u) { return u == fa[u] ? u : fa[u] = getroot(fa[u]); } void dfs(int u, int f) { vis[u] = true; for (int i = h[u]; i; i = e[i].nxt) if (e[i].to != f) dfs(e[i].to); for (int i = 0; i < q[u].size(); ++i) { int to = q[u][i].first, id = q[u][i].second; if (vis[to]) ans[id] = getroot(to); } fa[u] = f; } int main() { cin >> n; for (int i = 1, u, v; i < n; ++i) cin >> u >> v, add(u, v), add(v, u); for (int i = 1; i <= n; ++i) fa[i] = i; cin >> q; for (int i = 1, u, v; i <= q; ++i) { cin >> u >> v; q[u].emplace_back(make_pair(v, i)); q[v].emplace_back(make_paur(u, i)); } dfs(1, 0); for (int i = 1; i <= q; ++i) cout << ans[i]; return 0; }求 LCA 加强版给定一棵 $n$ 个点的树和 $q$ 次询问，每次给定 $u$，$v$ 和 $w$，求以 $w$ 为根的情况下 $u$， $v$ 的 LCA。$n,q \le 10^5$。以 $w$ 为根的树上 $u$，$v$ 的 LCA 只有五种可能：$u$、$v$、$w$、以 $1$ 为根 $u$、$v$ 的 LCA，以 $1$ 为根 $u$、$w$ 的 LCA，以 $1$ 为根 $v$、$w$ 的 LCA。为什么是五种？一定有两个是一样的。这些点和他们之间的关系又被称为 $u$，$v$，$w$ 构成的“虚树”。求出这五个点，特判即可。
更佳的阅读体验：2023 国庆集训 Day 3A 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。线段树多用于辅助数据结构。也有应用线段树思维的分治。矩形叠加问题给定一个 $n \times n$ 的二维平面上的 $m$ 个矩形，对于 $i=1,2,\cdots n$，求所有满足 $x=i$ 的整点中最多被矩形覆盖的整点被多少个矩形覆盖。$n, m \le 10^5$。把 $x$ 维看作是时间，$y$ 维看成一个一维的序列 $a_1, a_2, \cdots a_n$，问题变成：对于一个 $x \in [x_l, x_r]$，$y \in [y_l, y_r]$ 的矩形，相当于是在 $x_l$ 时间对区间 $[y_l, y_r]$ 的 $a$ 全体加 $1$，在 $x_r + 1$ 时间对区间 $[y_l, y_r]$ 的a全体减 $1$。然后对于时间 $1 \cdots n$，询问一下全局所有 $a$ 的最大值。LOJ Round #6 - 花火第二种操作在什么时候执行效果都是一样的，所以考虑一开始就交换两个数。对于一个排列，交换相邻的两个数从而排序所需要的数是确定的——逆序对数。所以我们的问题变成交换两个数使得逆序对个数最少。如果我们交换第 $l$ 个数和第 $r$ 个数，只需要考虑 $[l, r]$ 之内的逆序对改变，因为其他逆序对都没变。不失一般性假设 $h_l > h_r$（反之则没必要交换），减少的逆序对是 $[l, r]$ 中值在 $[h_r + 1, h_l - 1]$ 的数的个数 $\times 2$。也就是说对于每个 $h_i$，在二维平面中画一个点 $(i, h_i)$，我们想找两个点组成矩形的左上角和右下角，能框住最多多少个点。所以现在题面变成，给定平面上 $n$ 个点 $(x_1, y_1) \cdots (x_n, y_n)$，求两个点分别作为左上角和右下角最多能框住多少个点。那么如果 $x_i > x_j, y_i > y_j$，则 $(x_j, y_j)$ 一定不会作为左上角。所以我们可以找出一条从左下到右上的、$x$ 坐标单调递增、$y$ 坐标单调递增的可以作为左上角的点的序列 $s_1, s_2, \cdots, s_k$。同理可以得到一条从左下到右上的、$x$ 坐标单调递增、$y$ 坐标单调递增可以作为右下角的点的序列 $p_1, p_2, \cdots, p_k$。可以发现每一个点 $(x_i, y_i)$ 会对左上角位于一个区间 $s_l, \cdots, s_r$ 和右下角位于一个区间 $p_x, \cdots, p_y$ 的所有矩形有 $1$ 的贡献，直接用之前的矩形叠加问题即可解决。线段树分治考虑一类问题，给你一堆加入、删除操作，维护某个东西。如果加入、删除的数据结构非常困难，但是加入、撤销上一次加入很简单，且问题离线，就可以用 $\log$ 的时间代价使用一种简便的方法。具体方法是考虑某一元素的加入时间 $st$，和删除时间 $ed$。对时间建立一个线段树，把每一个元素的时间段 $[st, ed]$ 放在线段树上变成 $\log$ 个区间，然后在线段树上从上到下直接使用加入、撤销数据结构维护答案。动态连通块个数维护一张无向图 $q$ 次操作，每次加入一条边或删一条边，维护连通块个数。$q \le 10^5$。对每一条边存在的时间建立线段树。考虑线段树分治，对每一条边计算加入删除时间，然后在线段树上从根往下只需要支持加入一个边，撤销上一条边。此时只需要使用按秩合并即可以 $O(n \log^2 n)$ 的复杂度解决。HASHExample 1给定串 $S$ 和 $q$ 次询问，每次询问两个位置 $l_1, l_2$ 的最长公共前缀。$\lvert S \rvert, q \le 3 \times 10^5$。对于字符串，在 $i$ 的 HASH $h_i = (\sum_{j = 0} ^ i a^{i - j} s_j) \mod p$，则对于一个区间 $[l, r]$ 有 $\text{hash}([l, r]) = (h_r - h_{l - 1}) a^{r - l} \mod p$。CF1017E考虑求出凸包后，用一些旋转、平移无关的量表示。一种可行的方法是，考虑凸包上相邻的三个点，把这个三角形的三边长度作为参数构建一个序列，然后只需要看两个序列是否平移同构，直接 HASH 即可（也可以KMP）。这题提示我们，使用 HASH 的一个要点是找到一种表示。CCPC2023 D（矩阵 HASH）给定一个有 $m$ 种括号的长度为 $n$ 的序列，每种括号分为左右两种，有 $q$ 次操作，每次操作有两种情况：修改一个位置的括号类型（哪一种，左 / 右）。询问一段区间 $[l, r]$ 的子串是否是一个合法的括号序列，合法的括号序列定义如下：空串是合法的括号序列。如果 $A$ 和 $B$ 都是合法的括号序列，那么 $AB$ 也是。如果A是合法的括号序列，那么 $(A), [A], )A(, ]A[$ 也是合法的括号序列。$n, q \le 10^5$。给每一种括号随机对应一对矩阵，第 $i$ 种括号的左括号对应矩阵 $T_i$ ，第 $i$ 种括号的右括号对应矩阵 $T_i^{-1}$（$T_i$ 的逆）。这样的话一个括号序列 $A$ 合法则对应矩阵连乘是单位阵，反之则以极大概率不是单位阵。用线段树维护矩阵连乘即可。UOJ552 - 同构判定鸭给定两张有向图 $G_1$，$G_2$，每条边上有小写字母。定义一个串 $S$ 是好串当且仅当 $S$ 作为一条路径上的字母序列在 $G_1$ 中出现次数等于其在 $G_2$ 中的出现次数。求出最短的非好串（同样短按字典序），没有输出 $\texttt{Same}$。$n \le 500, m \le 3000$。对于给定长度 $l$，求所有 $\le l$ 的串出现次数是否一样？二分答案 $l$，判断是否所有小于 $l$ 的路径的字符串集合一样，上界 $n_1 + n_2$。令 $f_{i,j}$ 表示从 $i$ 出发，所有长度等于 $j$ 的路径的字符串集合的 HASH， $g_{i, j}$ 表示从 $i$ 出发，所有长度等于 $j$ 的路径的字符串的集合大小。对于每个长度、每个点记录所有以它为起点的所有串的 HASH 和，然后比对所有点的 HASH 和即可。对于计算答案，我们可以先计算出答案长度 $L$（可以证明不超过 $n_1 + n_2$），然后按照字典序枚举每一位 $i$，用之前算过的，每个点长度为 $L - i$ 的串 HASH 之和来验证。这里的 HASH 由于是串的和，所以不能使用传统的 HASH 方法（多项式hash）。因为多项式 HASH 是按位独立的，即 $H(\texttt{ab}) + H(\texttt{cd}) = H(\texttt{ad}) + H(\texttt{cb})$。可以使用矩阵 HASH。矩阵 HASH对于每个字母 $c$，随机一个低维矩阵 $M_c$。对于一个字符串，HASH 就是每一位对应的 $M$ 按顺序乘积。这样的 HASH 具有非常强的安全性（不满足交换，且不按位独立，同时自然 HASH 空间大），但是坏处就是计算常数大。
更佳的阅读体验：2023 国庆集训 Day 2A 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。搜索LOJ 10020 - 小木棍满足 $nm = \sum a_i = N$， 则需要满足 $N \mod n = 0$。较劣方案：使用 DFS 一根一根构造木棍。代码实现注意细节。#include <bits/stdc++.h> using namespace std; const int N = 70; int n, a[N], L; bool vis[N], flag; void dfs(int s) { // s - 当前木棍长度 bool ok = 0; for (int i = 1; i <= n; ++i) if (!vis[i]) ok = false; if (ok) return flag = true, void(); for (int i = 1; i <= n; ++i) if (!vis[i] && s + a[i] <= L) { vis[i] = 1; s += a[i]; if (s == L) s = 0; dfs(s); if (!s) s = L; s -= a[i]; vis[i] = false; if (flag) return; } } int main() { // read. sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1); int sum = 0; for (int i = 1; i <= n; ++i) sum += a[i]; for (int i = a[1]; i <= sum; ++i) if (!(sum % i)) { L = i; flag = false; dfs(0); if (flag) return cout << i << '\n', 0; } return 0; }搜索优化思路：减少状态数、减少状态处理时间（较难）。分治逆序对使用归并排序。思考题：对有序数列随机交换 $k$ 次，求逆序对的期望个数。归并排序。贪心局部最优解 = 全局最优解。反例：背包问题，局部最优解 $\ne$ 全局最优解。Example有 $n$ 个怪物，每个怪物有攻击力 $a_i$ 和 $b_i$，每一轮可以对一个怪物造成 $1$ 的伤害，每个怪物会对你造成 $a_i$ 的伤害，求你受到伤害最小的攻击顺序，$n \le 10^5$。优先打 $\frac{a_i}{b_i}$ （攻血比）较高的。如何证明？考虑反证法。如果先打攻血比较低的，受到的伤害一定不小于先打攻血比高的。如果 $\frac{a_i}{b_i} < \frac{a_{i + 1}}{b_{i + 1}}$，则原受到 $b_i(a_i + a_{i + 1}) + b_{i + 1}a_{i + 1}$ 的伤害，交换后受到 $b_{i + 1}(a_i + a_{i + 1}) + b_i a_i$，整理后得到 $a_{i + 1} b_i$ 和 $a_i b_{i + 1}$，则有 $a_{i + 1} b_i > a_i b_{i + 1}$。快速幂任意满足结合律的都可以使用快速幂。递归实现：ll qpow(ll a, ll b) { if (!b) return 1; ll res = qpow(a, b >> 1); res = res * res % p; if (b & 1) res = res * a % p return res; }循环实现：ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p, b >>= 1; } return res; }龟速乘 / 快速乘ll mul(ll a, ll b) { if (!b) return 1; ll res = 0; whlie (b) { if (b & 1) res = (res + a) % p; a = (a + a) % p, b >>= 1; } return res; }矩阵快速幂有结合律，但无交换律。可用于求较大的递推。Example. 求斐波那契数列在模 $p$ 意义下的第 $n$ 项。ST表用于处理 RMQ 问题。Example给定一个序列，询问区间最小值，$n \le 10^5$，$q \le 10^7$。要做到 $O(1)$ 询问，则预处理出 $f_{i,j}=\min_{k\in[i,i+2^i)} a_k$。LCATarjan.记录每个点的深度。先把较低点抬高，使得两点位于同一深度。