标签:问题模型
6 个条目
-
概念 多重背包
每种物品有数量上限;在容量约束下选择件数,最小化总费用;给出 f(i,j) 转移、边界与变式。
2026-11-13 -
概念 二维支配最值
给定平面点集,对每个点求其严格右上方点中 x+y 的最小值;按 x 降序扫描,用线段树维护后缀最小值。
2026-11-12 -
隐式稠密图上用 Borůvka 的 O(log n) 轮,把每轮化为最优出边 oracle;具体谓词结构与 SOS DP 见实例页。
2026-11-10 -
Borůvka 隐式图模型的实例索引:主理想、Rectilinear MST、XOR-MST,以及通用的紧凑最值查询条件。
2026-11-10 -
Borůvka 隐式图模型中以主理想为核心的 oracle 实例:布尔格 Zeta 变换 / SOS DP、树形偏序子树最值、DAG 可达性的双主理想。
2026-11-10 -
概念 补图连通性
给定稀疏图,求补图的连通块;用未访问集合做 BFS,间接遍历稠密补图,O((n+m) log n)。
2026-11-10