更佳的阅读体验：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$ 上，这样避免了矩阵乘矩阵。

二维 RMQ

Example 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。

LCA

Tarjan 算法

• 先把 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$ 构成的“虚树”。
• 求出这五个点，特判即可。