题目
按来源、难度和前置知识整理的题目页。
-
构造长度 N^2 的序列,每个 i 出现 N 次且第 i 个 i 在 x_i;按 x_i 排序后从左右两端贪心填数。
-
树上拓扑序最小逆序对;按块中 0/1 数量比贪心,把最优块并入父块,优先队列加并查集维护。
-
把 2N 个数配成 N 对,最小化 (x+y) mod M 的最大值;排序后二分分段,段内首尾配对。
-
在加减表达式中任意加括号使结果最大;只需要考虑减号后的括号,括号层数不超过两层,三状态 DP。
-
把行列建成二分图,卡片是边;可行选择等价于伪森林,按权值降序用带环标记的并查集贪心求最大权伪森林。
-
硬币面值都是 2 的非负整数次幂;按面值从大到小取硬币,最小化凑出每个询问金额的硬币数。
-
移动糖果等价于给前缀和加一或减一;枚举总和的质因子 k,把每个前缀和调整到最近的 k 的倍数。
-
区间平均化操作;答案是前缀和点集下凸壳的斜率,用单调栈维护分段平均,交叉相乘避免浮点。
-
只在检查日充钱;维护余额可达区间,区间全负时强制充一次,否则抬高下界,得到最少充钱次数。
-
题目 分组选择
每组至多选一个带权元素,按权值降序加入;是贪心选择模型的最小入门题,也是划分拟阵的实例。
-
题目 区间覆盖
用最少的给定区间覆盖目标区间;按左端点排序,每次选择能接上且右端点最远的区间。
-
题目 区间划分
把所有区间分配到最少机器,使同一机器上的区间不重叠;答案等于最大重叠深度,按左端点排序并用小根堆维护结束时间。
-
题目 区间点覆盖
选择最少的点,使每个区间至少包含一个点;按右端点排序,在未覆盖区间的右端点放点。
-
题目 区间调度
选择最多两两不相交的区间;按右端点升序,能选就选,交换论证给出最优性。
-
题目 国王游戏
重排大臣顺序,最小化最大奖励;按左右手数字乘积升序排序,高精度计算。
-
题目 排队接水
按接水时间从小到大排序,使总等待时间最小;相同时间按编号升序。
-
题目 消防局的设立
树上选最少的点,使每个点到某个选中点的距离不超过 2;按深度从大到小,在未覆盖点的爷爷处放消防站。
-
题目 随机数生成器
生成棋盘排列后,按数值从小到大尝试选格;维护每行可选列区间,得到排序后字典序最小的右上/右下路径序列。
-
题目 最大 K 子段和
支持区间覆盖和区间内选至多 k 个不相交子段;线段树维护最大/最小子段和,反复取最大子段并取反。
-
题目 最小逾期任务
单机非抢先调度中最小化逾期任务数;等价于选最大可准时子集,Moore–Hodgson 用最大堆反悔最长任务。
-
题目 多机区间调度
有 m 个学生和 n 个任务区间,每个任务至多一人完成,最大化可完成任务数;按结束时间排序并分配给最晚可接的学生。
-
题目 单位时间任务调度
每个任务耗时为 1、有截止期和利润,选择可准时完成的任务使利润最大;按利润降序用并查集找最晚空位。
-
题目 加权单机区间调度
单机选择不重叠区间,使总权值最大;按右端点排序,用 DP 加二分前驱求解。
-
题目 加权多机区间调度
把带权区间分配到 m 台相同机器,使同一机器上区间不重叠且总权值最大;用最小费用最大流求解。
-
区间内选两个数,用最少乘除质数操作使乘积为完全平方;按右端点扫描,维护每个 gcd 的最大下标与答案前沿。
-
题目 Earthquake
每条边有成本 c 和时间 t,最大化 (f - Σc) / Σt;二分答案后把边权改为 c + p t,用最小生成树判定。
-
平面完全图边权为曼哈顿距离;算法一用 8 个八分圆候选边 + Kruskal,算法二用四象限 Borůvka。
-
题目 矩形并
给定若干轴对齐矩形,求并的面积和周长;按 x 扫描,用线段树维护 y 方向覆盖长度与连通分量数。
-
题目 01-MST
完全图边权只有 0/1,给定权值为 1 的边;MST 权值为 0 边补图的连通分量数减 1。
-
把操作转化为最大生成树,用 Borůvka + max-plus Zeta 变换(SOS DP)求最大边。
-
题目 Envy
多次询问一组边能否同时属于某棵 MST;按权值分组,用 Kruskal 的连通块不变性和可撤销并查集判定。
-
平面点集的完全图边权为欧氏距离;用 Delaunay 三角剖分 + Kruskal 在 O(n log n) 时间求 MST。
-
构造 m 条边的连通简单图,边权为 a_u a_v;先求 MST,再用排序后的点权多路归并选剩余最小边。
-
双权瓶颈路径:最小化路径上 max a + max b;按 a 排序,用 LCT 动态维护按 b 的 MST。
-
题目 最小差值生成树
边权极差最小的生成树;排序后滑窗得到加删边区间,二分答案并用时间分治与可撤销并查集判定。
-
题目 XOR-MST
完全图边权为异或值;用 Borůvka + 可删除二进制 trie,每轮查询块外最小异或边,O(B n log n)。