趣题摘记-算法题精选-2

这一系列文章记录了我遇到过的一些趣题。

文章内容	简介
奇思妙想	数学和计算机领域，通过小小思考后能豁然开朗的趣题。
概率和期望	数学和计算机领域，与概率和期望相关的趣题。
算法题精选-1	OI/ICPC 向的算法题，去其琐碎、留其精髓，望博君一笑。
算法题精选-2	OI/ICPC 向的算法题，相比上一期题意更简洁，出处往往不可考。

按机器得金币

题意：有 $n$ 台机器。第 $i$ 个机器在前三次被按下时，分别掉出 $a_i,b_i,a_i$ 个金币，第四次开始不会掉金币。对于每一个 $k=1,2,\dots,3n$ 都要询问：如果按正好 $k$ 次，最多能掉出多少金币。 $n \le 10^5,v \le 10^9$

题解：每个机器的选择之间有限制，不利于分析。一台机器的四阶段顺序事件 $(0,+a_i,+a_i+b_i,+2a_i+b_i)$ ，可以 等价于 两个独立的金币掉落事件（ $a_i,a_i+b_i$ ），即后者的 $2^2$ 个状态正好对应前者 $4$ 个阶段。现在条件就转化成：有 $n$ 个代价为 $1$ ，收益为 $a_i$ 的事件；以及 $n$ 个代价为 $2$ ，收益为 $a_i+b_i$ 的事件。从大到小排序后贪心即可，要不加入一个代价为 $1$ 的事件，要不弹出一个代价为 $1$ 的事件并加入一个代价为 $2$ 的事件。

有向图可达点的比较

题意：给出一个有向图（可能会有环），每次询问 $x$ 能到的点和 $y$ 能到的点谁比较多。保证每次询问满足两者的相对差值较大。 $n,m,Q \le 5 \times 10^6$ 。From Claris。

经典定理： $k$ 个 $[0,1]$ 的随机实数的期望最小值是 $\frac{1}{k+1}$ 。

题解：注意有向图的准确可达点数量只能暴力（bitset）求。为每一个点随机一个 $[0,1]$ 的实数， $O(m)$ 求出每个点在可达点里的实数最小值 $\min_i$ 。询问时只需比较 $\min_x$ 和 $\min_y$ 大小关系即可。多随机几次打擂台。

区间平面最近点对

题意：平面上 $n$ 个整点，询问 $[l_i,r_i]$ 的平面最近点对（欧几里得距离最小）。 $n,q \le 25000,|x_i|,|y_i| \le 10^8$ 。

来源：Ynoi2002 Adaptive Hsearch&Lsearch。

前置：期望线性的平面最近点对网格算法，可见 OI WIKI。假设前 $i-1$ 个点的最近点对距离为 $s$ ，以 $s \times s$ 的网格做平面划分，并把前 $i-1$ 个点都塞入对应的网格中。检查第 $i$ 个点所在网格的周围 $9$ 个网格并更新答案，注意到每个网格里最多落入四个点，所以需要检查的点数是 $O(1)$ 的。检查过程中，如果答案被更新就重构网格图。

前置复杂度分析：前 $i$ 个点中最近点对包含点 $i$ 的概率是 $O(\frac{1}{i})$ ，重构网格的代价是 $O(i)$ ，总复杂度 $O(n)$ 。

直接转化：把所有点分块，预处理出从任意点开始、每个块结尾的网格数据，查询时暴力插入前面零散的点。根据上述分析，每一次差点触发网格重构的均摊代价是 $O(1)$ ，所以总复杂度是 $O((n+q)\sqrt n)$ 。

标准做法：假设最近点对距离 $d$ 满足 $d \le s$ ，那么按 $s \times s$ 划分的网格能求出 $d$ ，但当 $d$ 过小时要检查的点数量过多。这启发我们按 $2^0,2^1,\dots,2^k,\dots$ 分别划分网格， $2^k \times 2^k$ 的网格负责解出 $2^{k-1} < d \le 2^k$ 的答案，小的 $d$ 由更小规模的网格求解，即我们可以在点数较多的格子里删至 $O(1)$ 个点保持时间复杂度。按编号从小到大加点，每个点会在每级网格里各贡献 $O(1)$ 个点，即 $O(\log V)$ ；插入点 $i$ 时，它和前面某些点会构成最近点对的判定，例如和 $j$ 的距离是 $dis(i,j)$ ，就在数据结构里插入这组贡献；当触发网格删点时，优先删除最先插入的点；插入点 $i$ 后，考察所有 $r=i$ 的询问， $l$ 的答案记为数据结构里 $[l,i]$ 的区间最小值。我们要支持 $O(n\log V)$ 次插入、 $O(q)$ 次询问，分块复杂度为 $O(n \log V+q \sqrt n)$ ，树状数组复杂度为 $O(n \log V \log n+q \log n)$ 。

最大团

题意： $n$ 个点 $m$ 条边的无向图，求最大团的大小。 $n,m \le 200$ 。来源：叉姐 2015 ICPC Camp。

题解：求最大团的经典方法是 Bron-Kerbosch 爆搜，复杂度为 $O(3^{n/3})=O(1.44^n)$ ，本题显然 $n$ 过大。

注意到 $m$ 很小，节点总度数只有 $2m=400$ 。取阈值 $d=20$ ，把所有点按度数分成大点和小点。

如果最大团包含至少一个小点。枚举小点，显然最大团集合必然属于该点的邻点集合， $O(2^d)$ 枚举验证。
如果最大团不包含任何小点。显然最大团集合必然属于大点集合， $O(2^{2m/d})$ 枚举验证。

综上，得到最大团的一种复杂度为 $O(2^{\sqrt{2m}}\cdot nm)$ 的分块爆搜做法。

强连通图删边

题意： $n$ 个点的有向强连通图，问选三条边删除使不强连通的方案数。来源：2023 hdu多校 3C Leshphon。

题解：首先如何判断一张图是否是强连通？只需判断 $1$ 是否能到所有点，以及所有点是否能到 $1$ 。注意这个 BFS 可以从 $O(n^2)$ 优化到 $O(n^2/w)$ 。接下来考虑计数。如果图是强连通的，考虑之前遍历得到的两棵 BFS 树，显然所有树边中至少得删除一条才能使图不再强连通。在 $O(n)$ 条树边中任意枚举一条，然后递归成子问题。

假设删除 $k$ 条边，一共要递归 $k$ 层，每层 $O(n)$ 个子问题，底层 $O(n^2/w)$ 检查，总时间复杂度 $O(n^5/w)$

三维箱子的碰撞

题意：给出三维空间中 $N$ 个尺寸相等的长方体箱子，第 $i$ 个覆盖 $[a_i,a_i+L] \times [b_i,b_i+W] \times [c_i,c_i+H]$ 。判断是否存在两个箱子有公共部分。 $N \le 10^6$ 。From Claris。

题解：将三维空间划成 $L \times W \times H$ 的格子单元，把第 $i$ 个箱子放入 $(\lfloor \frac{a_i}{L}\rfloor, \lfloor \frac{b_i}{W}\rfloor, \lfloor \frac{c_i}{H}\rfloor)$ 的格子中。显然一个格子里最多只能放入一个箱子，否则必然有冲突。然后枚举每个有箱子的格子周围 $6$ 个格子判断是否有交。

最长回文子串

题意：给出一个长度为 $N$ 的字符串。对它的每个前缀都求最长回文子串的长度。 $N \le 10^6$ 。From Claris。

题解：令 $F_k$ 表示 $S[1\dots k]$ 的最长回文子串长度。有结论 $F_{k-1} \le F_k \le F_{k-1}+2$ 。每次扩展时，只要暴力 Hash 检查 $S[k-F_{k-1}-1\dots k]$ 和 $S[k-F_{k-1}\dots k]$ 是否是回文串即可。时间复杂度 $O(N)$ 。

(max, +) 卷积

题意：给出两个长度为 $N$ 的数组 $A,B$ ，求一个长度为 $N$ 的数组 $C$ 使得 $C_i=\max \limits_{0 \le j \le i}(A_j+B_{i-j})$ 。

$N \le 10^5$ ， $A$ 和 $B$ 的每一项都在 $[0, 10^9]$ 均匀随机。

题解：由于是 $(\max,+)$ 卷积， $A$ 和 $B$ 中越大的数越有用。取 $S=A$ 中第 $k$ 大的数 $+B$ 中第 $k$ 大的数。找出所有满足 $A_i+B_j \ge S$ 的二元组 $(i,j)$ ，更新 $C_{i+j}$ 的值。最后检查 $C$ 中的每一项：

如果它被更新过，那么已经得到了这个位置的最优解。
如果它没被更新过，直接按定义 $O(N)$ 计算它的值。

随机数据下，满足 $A_i+B_j \ge S$ 的二元组期望数量是 $O(k^2)$ ，概率为 $\int_0^{k/N} x \ dx=\frac{2k^2}{N^2}$ 。下面分析 $C[0\dots N]$ （ $C[N+1\dots 2N]$ 类似）。如果 $C_i$ 被剩下，那么它对应二元组均不满足条件，概率为 $(1-\frac{2k^2}{N^2})^{i+1}$ 。

按定义暴力计算所有剩下项的期望时间为：

$\sum \limits_{i=0}^N (1-\frac{2k^2}{N^2})^{i+1}(i+1)=O(1/\ln^2(1-\frac{2k^2}{N^2}))$

期望总时间复杂度为 $O(k^2+1/\ln^2(1-\frac{2k^2}{N^2}))$ 。为了最小化期望时间复杂度，有 $k^2=1/\ln^2(1-\frac{2k^2}{N^2})$ 。

$-k=1/\ln(1-\frac{2k^2}{N^2}) \rightarrow -\frac{1}{k}=\ln(1-\frac{2k^2}{N^2}) \rightarrow e^{-1/k}=1-\frac{2k^2}{N^2}$

把左式泰勒展开，有 $1-\frac{1}{k}=1-\frac{2k^2}{N^2}$ ，得 $k^3=\frac{N^2}{2}$ ，即 $k \approx O(N^{\frac{2}{3}})$ ，总时间复杂度约为 $O(N^{\frac{4}{3}})$ 。

木棒拼三角形全家桶

题意： $n$ 根木棒，长度分别是 $d_i$ ，从中选出三根使得拼成的三角形面积/周长最大/小。

周长最大：此题我曾出在 2018 百度之星A 第一题。考察最长的三根木棒 $(a,b,c)$ ，若 $a+b>c$ 则得到最优解，否则 $c$ 一定是无人企及的存在，删除它并递归处理即可。

等价于：对木棒排序后从后往前检查相邻三根，复杂度 $O(n \log n)$ 。

周长最小：对木棒排序后，设答案是 $d_i \le d_j \le d_k(i <j<k)$ ，从小到大枚举 $j$ ，显然 $k=j+1$ 。在左侧二分出 $i$ 使得 $d_i > d_{j+1}-d_j$ ，复杂度 $O(n \log n)$ 。

面积最大：枚举最长边 $c$ 。假设枚举了次长边 $b$ ，考虑旋转 $b$ 时能拼上去的所有的最短边 $c$ 。显然 $\angle C \le 90°$ ，所以 $c$ 一定越长越好。问题转化成：对木棒排序后，从小到大枚举 $k$ ，要快速找到最优的 $j$ 使得 $S(d_{j-1},d_j,d_k)$ 最大。考察相邻 $j$ 的面积，即 $S(d_{j-1},d_j,d_k)$ 和 $S(d_j,d_{j+1},d_k)$ ，用类似的推理可得后者必然优于前者。

等价于：对木棒排序后检查相邻三根，复杂度 $O(n \log n)$ 。

面积最小：此题我曾在 opentrains 一场比赛中做过，当时有额外限制 $n,\max{a_i} \le 10^5$ 且每一种长度不重复。当时的题解是：不妨设三条边 $a < b < c$ ，枚举 $c-b$ 的值 $d$ 。

假设已经知道了 $a$ ，三条边就是 $a, b, b + d$ ，显然 $a$ 固定时 $b$ 越小面积越小（证明：把 $a$ 这条边放在双曲线的两个焦点上，另外一个点正好落在双曲线上，面积与高度成正比，显然服从单调的关系）。
假设已经知道了 $b$ ， $a$ 显然越小越好（要保证 $a>d$ ）。

注意 $(a,b)$ 都是只和 $d$ 关联，彼此可独立考虑。所以枚举 $d$ 后 $a$ 和 $b$ 都能直接确定，其中 $a$ 是满足 $>d$ 的最小木棒长度， $b$ 是满足 $(b, b + d)$ 都存在的最小木棒长度。后者用 bitset 加速。复杂度 $O(\frac{n^2}{64} + n \log n)(n \sim V)$ 。

查找交集最大的一组人

题意：有 $n+1$ 个人， $2n$ 个物品。每个人正好喜欢其中的 $n$ 个物品。给出这些信息，找到某两个人 $(i,j)$ ，使得这两个人喜欢物品的交集的个数不小于 $n/2$ ，或报告无解。 $n$ 是偶数且 $n \le 6000$ 。

结论：随机选一对 $(i,j)$ ， $E[|S_i \cap S_j|] \geq n/2$ 。

证明：设第 $i$ 个人认为的好物品集合是 $S_i$ , 认为物品 $j$ 是好的人集合是 $T_j$ ：

$E[|S_i \cap S_j|] = E[\sum_{k=1}^{2n} [k \in S_i \cap S_j]] = \sum_{k=1}^{2n} E[[k \in S_i \cap S_j]] = \sum_{k=1}^{2n} \frac{\binom{T_k}{2}}{\binom{n+1}{2}}$

因为 $\sum_{k=1}^{2n} |T_k| = n(n+1)$ , 所以

$\sum_{k=1}^{2n} \frac{\binom{T_k}{2}}{\binom{n+1}{2}} = \frac{\sum_{k=1}^{2n} |T_k|^2}{n(n+1)} - 1 \geq \frac{n}{2}-0.5$

因为 $n$ 是偶数， $\geq n/2-0.5$ 等价于 $\geq n/2$ 。

题解：感性的想，多次随机 $(i,j)$ 时，总会随到 $|S_i \cap S_j| \ge n/2$ 。考察最坏情况： $E[|S_i \cap S_j|] = n/2$ ，且每次的交集要不是 $n/2-1$ ，要不是 $n$ 。那么前者和后者的比例是 $2:n$ ，即期望 $O(n)$ 次即可随机到答案，总时间复杂度为 $O(n^2)$ 。注意到本题还可以用 bitset 加速验证，即优化后的时间复杂度为 $O(\frac{n^2}{w})$ 。

卡内存版本的方格计数

题意： $n \times n$ 的矩阵，位置 $(i,j)$ 的权值是 $A_i \cdot B_j$ 。从 $(1,1)$ 走到 $(n,n)$ ，每次只能向右或者向下，问最大权值和能是多少，同时要求给出任意一组合法方案。 $n \le 10000$ ，内存限制 2MB。

常规做法：设 $f_{i,j}$ 表示到位置 $(i,j)$ 的最大权值， $g_{i,j}$ 表示该位置是从上还是从左转移过来的。 $f_{i,j}$ 显然可以用滚存做到空间 $O(n)$ ，但是 $g_{i,j}$ 不行，因为回溯方案的时候需要知道整个 $g$ 矩阵的信息。

优化一：bitset。由于 $g$ 中的信息只有 0 或 1，bitset 压缩后的空间是 $O(n^2/64)$ ，内存有所缓解但仍不能通过。

优化二：一种常被忽略的方法是利用时间换空间，即 $O(n^2)$ 计算每一步该怎么走，内存达标但时间 $O(n^3)$ 。

优化三：分块大法折衷！每 $S$ 行分一块，每次只计算一块的结果，时间 $O(n^3/S)$ 空间 $O(nS/64)$ ，还差一点！

优化四：分治大法！定义 $Solve(x_1,y_1,x_2,y_2)$ 表示对应矩阵的左上角走到右下角的最大权值和和方案。

设 $m=(l+r)/2$ ，用 $O((x_2-x_1)(y_2-y_1))$ 的时间求出从第 $m$ 行去第 $m+1$ 行时所在的列。
假设分割列是 $p$ ，递归 $Solve(x_1,y_1,mid,p)$ 和 $Solve(mid+1,p,x_2,y_2)$ 。

空间复杂度显然达标，时间复杂度是 $T(n)=O(n^2)+2T(n/2)=O(n^2)$ ，神奇！

动态 mex

题意： $n$ 个操作：1. 增加一个正整数；2. 删除一个已经添加过的正整数；3. 询问当前数字集合的 mex（最小的不在集合里的正整数）。给出一种 $O(n)$ 的做法，或证明不存在 $O(n)$ 的做法。

简化版：由于答案 $\le n$ ，增删数字的值域可简化成 $[1,n]$ 。我们还可以假设每个正整数最多只在集合中出现一次，因为我们可以用 $f_x$ 记录 $x$ 的出现次数，只有当 $f_x=1 \rightarrow0,0\rightarrow 1$ 变化时才需要更新答案。

结论和证明：不存在 $O(n)$ 的做法。构造一个“动态堆问题”：初始时堆里放了 $n$ 个数，分别是 $1,2,\dots,n$ ； $n$ 次操作，每次删除或增加一个数，或询问堆的最小值。显然对于任意一个“动态堆问题”，我们都能转化成对应的“简化版动态 mex 问题”（加删互换），即前者的复杂度下界一定是后者的复杂度下界。注意到 “动态堆问题” 涉及到的就是标准的堆操作，目前的共识是复杂度 $\Omega(n \log n)$ ，即证得“动态 mex 问题”不存在 $O(n)$ 的做法。

逆序对的另类求法

题意：给出 $n$ 个数，每个数的范围是 $[1,n]$ ，如何不用分治和数据结构求逆序对数量？

题解：给出一个基于二进制和桶排的做法：对于每一组逆序对 $(x,y)$ ，分别考虑 $a_x$ 和 $a_y$ 的二进制表示 $B_x,B_y$ 。因为 $a_x>a_y$ ，所以必然存在一个位置 $i$ ，使得 $B_{x,1 \sim i}>B_{y,1 \sim i}$ ——在位置 $i$ 处统计贡献。

整个算法分为 $O(\log V)$ 轮。每一轮执行以下操作：

从 $1$ 到 $N$ 遍历，如果 $a_x$ 是奇数就 $cnt_{a_x}++$ ，如果 $a_x$ 是偶数就 $ans+=cnt_{a_x+1}$ 。
每个数都对 $2$ 下取整。如果某个数变成 $0$ 了，下一轮将不再考虑。

显然总复杂度是 $O(n \log V+V)$ 。

边权为 1 的无向图最小环

题意：给出一张 $n$ 个点 $m$ 条边的无向图，每条边的长度都是 $1$ 。求图上长度不低于 $2$ 的最小环。

做法：熟知 Floyd 可以 $O(n^3)$ 求无向图或有向图的最小环，而本题其实存在 $O(n^2)$ 的做法。枚举最小环里的一个点 $s$ 跑 BFS，如果当前点 $x$ 的后继 $y$ 已经被遍历过，把 $f_x+f_y+1$ 更新答案并立即退出。对所有点都做一遍，取 min 即为最小环的大小。由于每个点最多被遍历一次，复杂度是 $O(n^2)$ 。

说明：设点 $s$ 所在的最小环环长是 $C_s$ ，最小环的环长是 $C_m$ ，如果不存在环则 $C=+\infty$ 。从 $s$ 开始 BFS 的结果只满足 $C_s \ge f_x+f_y+1\ge C_m$ ， $C_s=f_x+f_y+1$ 并不成立。例如，图 $1-2-3, 3-4-6, 3-5-6$ 中 $1$ 根本不在任何环里，上述做法还是会把 $f_4+f_5+1$ 更新答案。不过这一步并不会影响最小环的正确性，因为出现这种情况时一定存在环了，且当前值严格劣于最小环。

求k组出现了奇数次的数字

题意：已知 $N$ 个数中恰好有 $k$ 个不同的数字出现了奇数次。只能扫一遍，要求出这 $k$ 个数。 $N$ 很大， $k \leq 10$ ，内存很小。据说题目来自 NOI 国家队集训。

题解： $k=1$ 是异或， $k=2$ 是维护 $\log N$ 个异或，下面讲解 $2 < k \le 10$ 的做法。

子问题：先从一个入手。对于一个数字集合 $S$ ，如何判断是否只有一个数字出现了奇数次？除了要求速度快、内存小，还要求能动态增加数字，以及快速合并两个集合。

基于概率的子问题解法：取一个模数 $P$ （如 $998244353$ ）以及模域下的一个常数 $c$ 。

对于每一个进来的数 $x$ ，取一个映射 $y=xP+c$ ，维护 $y$ 的异或和 $xor_y$ 。如果只有一个数字出现了奇数次，必然有 $xor_y \mod P=c$ ；反之，我们可以认为不成立。同时维护 $x$ 的异或和可还原方案。多取几组 $(P_i,c_i)$ 后可以认为能稳定判断并还原，称这一套完整的机制为一个“判定机器”。

基于概率的原问题解法：维护 $m$ 个独立的判定机器（比如取 $m=20$ ），彼此独立。每次来了一个数字 $x$ 后，依次枚举判定机器，每个判定机器都有 $\frac{1}{2}$ 的概率插入这个数字。注意要保证相同的 $x$ 对于相同的判定机器“是否插入的行为”是一致的（如对 $x$ 施加哈希函数，用二进制位决定是否插入）。上述操作保证了：对于任何一个判定机器，总共出现了偶数次的数字一定插入了偶数次，总共出现了偶数次的数字（我们要求的数字）插入了偶数次还是奇数次的概率是均等的。 $N$ 个数字插入完成后，枚举判定机器里所有 $2^m$ 个子集。对于一个子集 $S$ ，合并对应的判定机器，看看总集合里 是否只有一个数字 $t$ 出现了奇数次。如果是，他必然是这 $k$ 个答案中的一个。枚举完所有子集后，汇总去重即为答案。

准确率证明：上述算法求得的答案必然正确，但是有概率漏解。考虑一个行数为 $k$ ，列数为 $m$ 的01矩阵。 $0$ 和 $1$ 表示这个答案 $t$ 在这个数字集里是否出现奇数次。如果能枚举到所有 $k$ 个答案，说明对于每一行，都存在至少一个列集合 $S$ ，满足列集合异或后是这一行的 one hot。进一步能推导出，这个矩阵满秩（在在异或空间下考虑问题）；反过来，如果该矩阵满秩，列向量就能组合出所有 $2^k$ 列向量，当然也能拼成 one hot。也就是说，能搜到所有解和矩阵满秩是充要的。问题转化成： $k \times m$ 的矩阵里每个元素出现 $0$ 和 $1$ 的概率均等，求其不满秩（出错）的概率。这个东西可以递推来求。固定 $k$ ，从小到大递推 $m$ ，我们有 $f_{k,0}=1,f_{k,i}=(1-f_{k,i-1})2^{i-1-k}$ 。回到题目 $k=10$ ，取 $m=20$ 时正确率 $99.7\%$ ， $m=25$ 时正确率 $99.997\%$ 。

和至少为 K 的最短子数组

题意：给出一个可能有负数的整数数组和一个阈值 $k$ ，找一个长度尽量小的子串使得和 $\ge k$ 。Leetcode 862

题解：前缀和后就是找 $\min \limits_{sum_r-sum_{l}\ge k}(r-l)$ 。对于 $l_1<l_2$ ，如果有 $sum_{l_1} \le sum_{l_2}$ ，则 $l_2$ 一定优于 $l_1$ （值更小长度也更小）。根据这个性质构建单调队列，查询 $r$ 时在单调队列中二分出最近的合法 $l$ ，复杂度 $O(N \log N)$ 。