李超线段树是用于维护平面内线段关系的树. 全局插入版本,插入操作的复杂度为 局部插入版本,插入操作的复杂度为 上述两个版本的查询复杂度均为
对于一个图,如果存在一条路径恰好经过所有边一次,则称这条路径为一条欧拉路径。 如果存在一条回路经过所有边恰好一次,则称这条路径为一条欧拉回路。 存在欧拉回路的图被称为欧拉图。 如果一个图的边集可以被分成若干个简单环,则称这个图可以环分解。 判定定理 1: 一个图存在欧拉回路当且仅当这个图可以被环分解。 充分性: 如果可
在埃氏筛中,我们会发现一个合数我们会筛多次,浪费大量时间,因此我们就会考虑,能不能让每个数只被筛一次?也就引出了欧拉筛,也就是线性筛. 线性筛保证了每个数只被其最小的质因数晒去.我们考虑算术基本定理, ,有 ,且 ,我们都用 去筛掉这个数,从而达成线性时间复杂度 洛谷模板 这里为什么要有i%p=\=0? 考虑当前从小到
网络流板子,来自 Obsidian 的算法笔记。
考虑一个大小为 的集合,其中前 个元素标记为红色,后 个元素标记为蓝色。 从这 个元素中任意选取 个元素的总方案数为 。 若按选出的红色元素个数 分类( ),则需要从 个红色中选 个,同时从 个蓝色中选 个,方案数为 。 对所有可能的 求和,二者必然相等。 1. 对称平方和: 2. 上指标求和 (朱世杰恒等式): 3.
考虑这样的一个问题,n个人互相送礼物,要求礼物不能留给自己,最后会有多少种方案数? 我们发现直接求解析式很难,需要用到容斥原理,因此我们考虑求递推公式, 令 为n个人互相送礼物的方案数.我们考虑第一个人a会如何送出手中的礼物.显然除自己外a有n-1种送出礼物的方案,假设送给了b,那么b有几种送礼物的方案呢? 1. 送给
多个进程/线程同时访问共享数据时,会产生竞态条件(Race Condition)。 例如: count++实际上不是一步: 如果两个进程交错执行: 最终: 而不是: 因此需要保证: 同一时间只能有一个进程进入修改共享数据的代码区域。 这个区域称为: 临界区(Critical Section) 一个正确的同步算法需要满足
本章核心问题: 程序看到的地址和真实内存地址为什么不同?操作系统如何管理内存?进程切换时 CPU、页表、TLB 如何协作? 早期系统中: 程序直接访问物理地址: 存在问题: 例如: 进程 A: 进程 B: 如果直接对应物理地址: 因此不同进程必须拥有独立地址空间。 假设连续分配: 虽然总空闲空间足够,但是不连续。 例如
