笛卡尔树

笛卡尔树是一种特殊的二叉树,由一系列键值对 构成。它同时满足以下两个特性: 1. 二叉搜索树(BST)性质:节点的左子树中所有节点的 值均小于根节点的 值,右子树中所有节点的 值均大于根节点的 值。 2. 堆(Heap)性质:节点的 值满足堆的性质(大根堆或小根堆)。通常在算法竞赛中,默认 满足小根堆性质,即父节点的

03-陪集-Lagrange-正规子群

设 是群 的子群。对于任意 : 1. 左陪集(Left Coset):集合 称为子群 在 中关于代表元 的左陪集。 2. 右陪集(Right Coset):集合 称为子群 在 中关于代表元 的右陪集。 元素 称为该陪集的代表元(Representative)。 陪集是用子群 作为基准结构对全群 进行的平移划分。陪集本身

04-商群与同态

设 是群 的正规子群( )。定义集合: 为 关于 的全体左(右)陪集构成的集合。 在集合 上定义二元运算(陪集乘法): 代数系统 称为群 关于正规子群 的商群(Quotient Group)。 商群是通过忽略正规子群 内部差异而构造的同余类系统。由于陪集是用其中的代表元来写出的,必须保证选取的代表元不同时,陪集相乘的结

抽象代数索引

本索引包含群论笔记的章节目录、依赖关系、定理速查、概念索引与符号表。 | 编号 | 笔记文件 | 主要内容 | 涉及定理 | |:---:|---|---|---| | 00 | 00-集合论与映射 | 集合、等价关系、划分、映射、选择公理、商集与良定性 | 定理 0.1 ~ 0.8 | | 01 | 01-群与子群

现代 CMake 实用笔记(面向 C++ 与 AI Infra)

这份笔记总结自小彭老师的课程及实际工程经验,删掉了冷门复杂的语法,只保留做 C++ 开发和 AI Infra(算子、推理引擎、CUDA 开发)必须掌握的核心内容。 很多人初学时容易把 CMake 和编译器搞混: - g++ / clang++ / nvcc 才是真正的编译器,负责把代码编译成汇编和机器码。 - CMak

0-1BFS扩展

给定一张无向图,起点为 ,终点为 。每条边的权值表示经过该道路所需时间,题目语境下普通道路耗时为 ,若需要聊天则额外耗时 ,因此边权只会落在小整数集合 中。图中可能存在重边,要求输出从 到 的最短路长度。 数据范围为 , 。若直接使用堆优化 Dijkstra,复杂度为 ,在该规模下常数和对数因子都较重;边权范围很小,应

2-SAT

有 个布尔变量 ,另有 个需要满足的条件,每个条件的形式都是「 为 true / false 或 为 true / false」。比如「 为真或 为假」、「 为假或 为假」。 2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。 成立 或 成立,等价于:若 不成立,则 必成立;且 若 不成立,则 必成立。 注意

Hall 婚姻定理 (Hall's Marriage Theorem)

设二分图 , 。 中存在包含 中所有顶点的完全匹配(即最大匹配为 )的充要条件是: 对于 的任意子集 ,其在 中的邻域集合 均满足: 若二分图不一定存在完美匹配,则 的最大匹配数为: 即我们只需要最小化亏损 。 如果 中的每个点 连向 中下标在某个区间 内的点,若区间满足连续包含性,根据 Hall 定理,只需检验所有连