Sshwy's OI 知识库
共 84 个概念 · 36 道题目 · 180 个标签 · 503 条关联
最近更新
-
概念 欧拉图
经过每条边恰好一次的图结构;无向图由奇度顶点个数判定,有向图还需入度与出度平衡且弱连通。
2026-11-20 -
概念 欧拉图判定
线性判断无向图或有向图是否存在欧拉回路或欧拉迹:无向图看奇度顶点与连通性,有向图看入度出度平衡与弱连通。
2026-11-20 -
概念 哈密顿图
经过每个顶点恰好一次的图结构;含哈密顿回路的图称为哈密顿图,一般图判定是 NP 完全的,Dirac 与 Ore 条件给出充分判定。
2026-11-20 -
用栈不断走未使用的边,回溯时把顶点追加到答案,反转后得到欧拉迹;时间与 n+m 成正比。
2026-11-20 -
概念 拟阵对偶
把拟阵的每个基取补集,得到对偶拟阵;对偶的基与原拟阵的基互为补集,秩函数有 r*(A)=|A|-r(E)+r(E-A)。
2026-11-18 -
概念 反悔贪心
先维护一个可行解,用堆、链表或残余结构保存反悔项;出现更优交换时替换旧选择,正确性由交换论证保证。
2026-11-17 -
概念 贪心选择模型
选择型贪心的集合模型:按代价非减序加入可行元素;安全选择与交换论证给出正确性条件,拟阵是充分条件。
2026-11-17 -
概念 最大拟阵交
求两个拟阵的最大公共独立集;在交换图上找增广路,二部匹配是两个划分拟阵的交。
2026-11-17 -
概念 最大子段和
求数组中和最大的连续非空子段;前缀和最小值与 Kadane 扫描给出两种等价视角。
2026-11-17 -
概念 唯一父状态堆枚举
把隐式状态空间组织成每个非根状态恰有一个父状态的树;父值不大于子值,堆按值弹出即可不重不漏地做第 k 小枚举。
2026-11-17 -
概念 二分图
顶点可分成两侧、所有边都跨两侧的无向图;等价于无奇环,可用二染色判定。
2026-11-17 -
概念 拟阵
有限集上满足遗传性与交换公理的独立集族;极大独立集称为基,秩是子集的最大独立集大小。
2026-11-17
标签
数学36贪心32图论25生成树18动态规划16并查集10拟阵10排序10区间9Borůvka8DP 优化8代数结构8交换论证7偏序集7堆7算法7最小生成树6计算几何6调度6问题模型6偏序5扫描线5Kruskal4Zeta 变换4二分答案4前缀和4实现4数据结构4树4线段树4BFS3DP3Delaunay3二分图3优先队列3决策单调性3凸壳3分数规划3分治3反悔贪心3序理论3构造3枚举3欧拉回路3欧拉图3欧拉路径3第k小3群论3SOS DP2Trie2三角剖分2二分2交换公理2位运算2动态 MST2匹配2半群2单调队列2可撤销并查集2图2基2多重背包2布尔格2幺半群2数论2最优化2最大子段和2染色2格2模拟2滑动窗口2直和2离线2线性函数2线性扩展2补图2覆盖2集合论201 分数规划11D/1D1Bellman 方程1DFS1Grothendieck 群1Hasse 图1Huffman1LCT1MDP1Monge1Prim1Sweep line1Voronoi1multiset1不动点1主理想1事件1二分栈1二进制1交换群1伪森林1凸包1函数空间1分组1分配格1判定1前缀最值1区间最值1区间查询1区间覆盖1半环1单交叉1单机调度1单调性1单调栈1原像1双权瓶颈路径1取模1变分1可行性1合并1哈密顿回路1哈密顿图1哈密顿路径1四边形不等式1回路1增广路1多集合1奇环1子集和1字符串1安全选择1对偶1对偶空间1截距1投影1抽象代数1拓扑排序1拟阵交1括号1按秩合并1斜率1斜率优化1无后效性1曼哈顿距离1最小生成森林1最小费用最大流1栈1模1模型1欧氏距离1泛函1深度1点覆盖1状态转移1独立集1环1理想1瓶颈生成树1瓶颈路径1直积1直线1矩形并1矩阵1笛卡尔积1等价类1索引族1纤维1线性空间1组合结构1网络流1群1群完备化1背包1自由交换群1自由群1表达式1记号1路径压缩1逆序对1选择1高精度1