跳到正文

CSCI2740

竞赛编程

区间查询与线段树、图搜索、连通性与最短路径、字符串匹配、数论、计算几何、动态规划、贪心算法及无偏游戏。

19 章 · 33 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 33 节已标记完成

下一节: 树状数组:区间、更新与前缀和

完成记录保存在此浏览器中。

这门课在网上

CSCI2740 笔记里的内容

定理卡
97
定义
54
反例
50
概念视角
17
思想史
0
证明透视
47

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 33 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

在网上定理卡 97 · 定义 54 · 反例 50 · 概念视角 17 · 证明透视 47

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 33 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

第 1 章 · 5 节

区间查询

从存储区间的不变量推导 Fenwick 树的查询与更新,证明对数时间界,并区分增量、赋值及最小值查询。

定理 12 · 定义 5反例 7视角 4证明透视 5

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 1.1

    树状数组:区间、更新与前缀和

    从存储区间的不变量推导 Fenwick 树的查询与更新,证明对数时间界,并区分增量、赋值及最小值查询。

  2. 1.2

    用线段树处理赋值与区间最小值

    证明线段树的不变量,以及单点赋值下对数时间区间最小值查询。

  3. 1.3

    线段树:结合式摘要与有序区间查询

    推导结合式摘要的有序线段查询,并区分单点更新和延迟传播。

  4. 1.4

    二维前缀和与矩形差分

    推导四角求和查询和离线矩形加法,明确处理左闭右开边界、空矩形及预处理成本。

  5. 1.5

    平方根分块:延迟加法与区间总和

    区分存储值、延迟的整块加量与真实区块总和,证明可交错执行的区间加法及总和查询。

第 2 章 · 1 节

2. 静态区间查询

预处理二的幂长度区间以查询静态最小值。

定理 3 · 定义 2反例 3证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 2.1

    静态区间最小值的稀疏表

    证明二的幂长度区间不变量,解释重叠最小值查询。

第 3 章 · 1 节

图的连通性

无向多重图的 DFS low-link 与桥边。

定理 2 · 定义 2反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 3.1

    无向多重图中的 DFS 桥边

    保留平行边身份,证明 low-link 桥边判据。

第 4 章 · 1 节

区间更新

以端点差分处理区间加法与单点值。

定理 1 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 4.1

    差分数组与区间加法端点

    证明离线区间加法的端点不变量,并联系 Fenwick 单点查询。

第 5 章 · 1 节

无偏游戏

有限正常玩法、mex 与异或。

定理 3 · 定义 2反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 5.1

    无偏游戏的 mex 值与异或

    证明有限无偏正常玩法游戏的异或法则,并跟踪取子游戏。

第 6 章 · 1 节

因数筛法

Möbius 因数和及互素配对计数。

定理 3 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 6.1

    Möbius 因数和与互素配对

    证明因数指示式,并以倍数筛计算互素索引对。

第 7 章 · 1 节

带权区间调度

由相容前缀建立动态规划。

定理 1 · 定义 1反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 7.1

    带权区间调度

    推导带权区间的前驱递推、重建及复杂度。

第 8 章 · 3 节

计算几何

利用方向与有向面积判断点相对于凸多边形的位置。

定理 9 · 定义 5反例 4视角 2证明透视 4

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 8.1

    有向面积与凸多边形中的点

    运用叉积、边界测试与鞋带和,明确说明凸性及整数范围假设。

  2. 8.2

    方向与闭线段相交

    精确分类线段相交,包括共线和退化情形。

  3. 8.3

    单调链凸包与共线点

    构造凸包极点并证明按列分组的单调链算法。

第 9 章 · 2 节

字符串算法

利用边界和回退搜索重叠字符串。

定理 9 · 定义 4反例 3视角 1证明透视 4

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 9.1

    KMP 字符串匹配:边界、回退与重叠匹配

    从嵌套的边界推导前缀函数,证明模式串搜索的线性时间复杂度,保留重叠匹配,并由最长边界求最小周期。

  2. 9.2

    Z 数组、区间复用与精确字符串匹配

    证明前缀匹配复用的线性复杂度,并用 Z 值求精确匹配、边界与周期。

第 10 章 · 3 节

图搜索与连通性

低链值、桥边、有向分量与删点。

定理 7 · 定义 5反例 6视角 1证明透视 7

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 10.1

    迭代低链值搜索与桥森林

    追踪以边编号实现的迭代低链值计算,并构造由桥连接的森林。

  2. 10.2

    强连通分量、完成顺序与缩点图

    推导两遍有向 DFS 算法及其无环缩点图。

  3. 10.3

    割点、DFS 根与删点后的连通分量数

    推导 low-link 删点判据并计算剩余连通分量。

第 11 章 · 1 节

二进制快速幂

循环不变量、模幂与矩阵应用。

定理 2 · 定义 1反例 2证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 11.1

    二进制快速幂:循环不变量、矩阵递推与游走计数

    不靠交换律证明二进制快速幂并应用矩阵幂。

第 12 章 · 1 节

单调队列

窗口极值、支配关系与均摊成本。

定理 3 · 定义 1反例 2证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 12.1

    滑动窗口最小值:支配、过期与单调双端队列

    证明支配关系、处理重复值并界定双端队列总工作量。

第 13 章 · 2 节

轻重链剖分

树路径、子树大小与区间查询边界。

定理 8 · 定义 4反例 4证明透视 4

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 13.1

    轻重链路径与查询边界

    证明轻边数量界,并把顶点及边路径划分为区间查询。

  2. 13.2

    祖先倍增、第 k 级祖先与最近公共祖先

    复合父节点映射的二次幂,证明求最近公共祖先时的同步跳跃不变量,并在不虚构根以上祖先的前提下回答静态树查询。

第 14 章 · 2 节

子集动态规划

精确已访问集合状态、路径代价与最优路线。

定理 8 · 定义 3反例 3视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 14.1

    子集状态、哈密顿回路与最优路线

    推导精确已访问集合动态规划并还原最优有向回路。

  2. 14.2

    递增子序列:最小尾值与有效见证

    证明最小尾值不变量,处理相等值,并重建真正的子序列而不是把尾值数组当作见证。

第 17 章 · 2 节

数论

同余式、中国剩余定理与线性筛法。

定理 5 · 定义 3反例 3视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 17.1

    精确算法:同余与几何定向

    用扩展欧几里得算法解线性同余式,在模数不必互素时合并同余式,并为定向测试与模幂保持精确的边界检查。

  2. 17.2

    线性筛:最小质因子与多次分解

    证明合数的唯一生成规则,构造最小质因子表,并明确预处理、输出和算术运算的成本。

第 16 章 · 3 节

最短路径

含负环的 Bellman-Ford,以及使用双端队列的 0-1 BFS。

定理 13 · 定义 7反例 4视角 3证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 16.1

    同步 Bellman–Ford:最短途径、负环,以及额外一轮所证明的内容

    证明 Bellman-Ford 背后的限长递推式,把距离分为有限、无穷及负无穷,并说明额外一轮所能证明的内容。

  2. 16.2

    0–1 BFS:为什么双端队列可以替代优先队列

    当每条边的成本为 0 或 1 时,用双端队列计算最短距离,并证明双键不变量、处理过时条目及分析复杂度。

  3. 16.3

    Dijkstra 与 Floyd–Warshall:单源与全点对最短路径

    证明非负权重下的 Dijkstra 算法,指出负权边究竟在哪一步令它失效,并推导计算全点对距离的 Floyd–Warshall 递推式。

第 15 章 · 1 节

搜索与答案二分

对单调可行性判断进行二分搜索。

定理 2 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 15.1

    对容量进行二分搜索:先证明可行性检验

    把最小化问题化为单调的是非判断,证明贪心可行性检验,并以安全的上下界与运算对答案进行二分搜索。

第 18 章 · 1 节

最小生成树

不相交集合、Kruskal 与 Prim,以及割性质。

定理 3 · 定义 3反例 1视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 18.1

    不相交集合、Kruskal 算法与 Prim 算法

    证明最小生成树的割性质,在不相交集合并查集上实现 Kruskal 算法,并与 Prim 算法比较。

第 19 章 · 1 节

贪心算法

区间调度与工作次序的交换论证。

定理 3 · 定义 3反例 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 19.1

    贪心算法与交换论证:区间调度与最优工作次序

    阐明贪心选择的证明模式,并以交换论证证明区间调度及按加权完成时间排序的贪心规则,同时说明为何看似合理的贪心规则会失败。

Vercel 访问统计与公开页面性能测量分别征求同意,均非使用网站的必要条件。

网站功能存储(按需使用)

安全、登录和你选择的偏好会按需使用存储,与可选统计分开处理。

撤回会停止后续统计;需要卸载已加载的统计程序时,页面会刷新。已发送的数据不会因此删除。

查看 Cookie 与存储详情