守株阁

从起点到一个顶点的当前最好路径，未必已经是最短路径。Dijkstra能永久确定当前距离最小的顶点，是因为后面的非负边不能把尚未发现的路径变得更短。允许负边以后，这项推理失效，优先队列本身无法补回缺失的前提。 本篇在同一个有向图接口上比较Dijkstra与Bellman–Ford，再用势函数说明怎样在保留路径比较的条件下消除负边。09篇的索引堆继续用于减键，22篇的状态依赖思想用于理解有边数限制的路径。 距离与路径证据 输入n≥1个顶点、m条有向整数权边以及起点s。顶点编号0到n−1，平行边和自环保留独立输入ID。输出每个顶点的距离和前驱边ID；不可达顶点距离为None，不能用一个可能被真实路径超过的有限大整数冒充无穷。 Dijkstra要求全图边权非负，发现负权就拒绝，即使负边位于当前起点不可达的分量。Bellman–Ford允许负边，但只在存在从s可达的负环时报告异常，并给出一个可核对的环。异常时不把尚在变化的距离数组作为最终最短距离交付。 没有可达负环时，任意最短路都可去掉非负环，得到至多n−1条边的简单路径。若某个负环可达，能通过它到达的顶点可以反复绕环降低路径权重，因此不...

把一张棋盘贴到倾斜平面上，外轮廓已经投影成梯形，内部格线却在三角形对角线处折弯。问题可能不在图片，也不在投影矩阵，而在投影之后仍然用屏幕重心坐标直接平均UV。 本篇用两个三角形表示同一个平面，保持几何、相机、覆盖规则和棋盘采样方式不变，只切换UV插值。除了两张结果图，还通过射线与平面相交独立求出UV，避免用同一个插值公式验证自身。 UV描述的是表面上的位置 纹理坐标u、v是从表面位置到二维纹理域的映射。本实验把平面四角分别标为(0,0)、(1,0)、(1,1)、(0,1)。u增加表示从左向右，v增加表示从平面近边走向远边。它们不是屏幕像素坐标，也不是相机距离。 棋盘在UV域分成8×8格，取floor(8u)与floor(8v)，两者之和的奇偶决定灰度。端点1钳制到最后一格，防止访问第8号格。这是明确选定的点采样和边界规则；本篇没有读取外部纹理图片，也没有双线性过滤。 两种灰度在线性域取0.04与0.8，最后通过第04篇的sRGB函数编码一次。因而本次比较不会混入“一个版本在线性域、另一个版本在显示码值域”的颜色差异。 屏幕中点不一定对应空间中点 先看一条边。空间端点A、B的w分...

22篇的带权区间调度不能总选最早结束的区间。Kruskal却可以反复选当前最轻、且不形成环的边，最终得到最小生成森林。区别不在于两个规则哪一个“更自然”，而在于是否能证明局部选择仍属于某个全局最优解。 本篇先给出割与交换证明，再把无环边集合抽象成图拟阵。教学实现复用10篇并查集，检查的是无环约束；优化目标的正确性需要另外证明。 无向多重图的目标 输入n个顶点，编号0到n−1，以及m条无向边(u,v,weight)。权重为整数，允许负权、相等权、平行边和自环；每个输入位置是独立边ID。输出总权重与选中的边ID。 若原图连通，目标是最小权生成树。若有c个连通分量，目标是在每个原分量内选生成树，合计n−c条边；孤立点也算分量。空图返回总权重0和空边集。 这不是在任意子图中最小化权重。允许任意森林时可以不连接某些顶点；允许任意连接子图且存在负权环时，加入额外边反而可能降低总权重。生成森林同时要求连接原分量与无环，两个条件都不能省略。 Kruskal只负责维持森林 将边按(weight,id)递增排序，开始时选边集A为空。扫描到边(u,v)时，用并查集判断两端是否已经连通：不连通就选入并合...

22篇先证明状态与转移正确，再计算每个状态。优化动态规划时，这个顺序仍然重要：减少内存不能丢掉未来依赖，缩小候选集合不能排除真正最优决策。观察几行最优下标递增，只能形成猜测，不能授权程序跳过剩余候选。 本篇把一个非负数组切成固定数量的非空连续段，最小化各段元素和的平方之和。先建立朴素递推，再证明特定代价满足的四边形不等式，最后用决策单调性减少搜索。 状态包含用了多少段 输入n个非负整数a，以及段数g。输出最小代价和g个半开区间，它们按顺序无缝覆盖[0,n)，每段非空。n=0、g=0单独返回代价0与空方案；其余要求1≤g≤n。 令S_i为前i项之和，S_0=0，区间[k,i)代价W(k,i)=(S_i−S_k)²。沿用11篇前缀和的半开语义，一次区间和只需相减；不需要再建一个区间求和数据结构。 D_t[i]表示前i项恰分成t段的最小代价。D_0[0]=0，其余零段状态不可行；对i≥t： Dt[i]=min⁡t−1≤k<i{Dt−1[k]+W(k,i)}.D_t[i]=\min_{t-1\le k<i}\{D_{t-1}[k]+W(k,i)\}. Dt​[i]=t−1≤k...

一组预约各占一个时间区间并带有收益。选出互不冲突的预约，使总收益最大。最早结束的预约为后续留下较多时间，但它可能收益很小；直接套用无权区间调度的贪心规则会丢掉更好的带权方案。 例如[0,1)和[1,2)的收益各为2，[0,2)的收益为5。最早结束的贪心可以选前两个，收益4；只选长区间却有5。动态规划需要保存的是尚未选择最后一个区间时，各个前缀能达到的最好收益。 输入、兼容与恢复结果 输入n个三元组(start,end,weight)，端点和收益为整数，要求start<end。区间采用半开语义，相接端点兼容：一个区间的end等于下一个的start时可以同时选择。收益可以为负或0，空方案始终合法。 每个输入位置是独立ID，相同区间也保留不同ID；它们有正长度且彼此重叠，不能同时选择。输出包括最优收益和一组实际选择的ID，ID按算法的结束时间顺序返回。目标并未要求所有最优解，也不要求ID字典序最小。 教学接口对start≥end抛出ValueError。特别是零长度区间没有直接混入常规区间证明：空区间怎样参与收益和兼容，需要另外约定，不能靠排序偶然得到结果。 为什么按结束时间建立...

两个长度接近n的系数数组做朴素卷积，需要约n²次乘法。把其中一个数组机械地切成两半，仍然需要与另一个数组的每个元素相乘，总工作不会减少。有效分治需要找到可以共享的中间结果，而不只是增加递归调用。 FFT利用单位根的成对结构共享多项式求值。本篇从卷积开始推导这项结构，再用选择问题对照另一种分治：不是加速合并，而是只递归进入包含目标的一边。两者的递推不能混写。 卷积等价于多项式乘法 输入实数系数数组a、b，长度分别为p、q；输出c长度p+q−1，其中 ck=∑i+j=kaibj.c_k=\sum_{i+j=k}a_i b_j. ck​=i+j=k∑​ai​bj​. 把A(x)=Σa_i x^i、B(x)=Σb_j x^j相乘，c正是乘积系数。空数组在教学接口中代表没有系数，任意一方为空时返回空结果；这个约定单独处理，避免长度公式产生负数。 朴素算法对每对(i,j)把a_i b_j加到c[i+j]。在单位成本实数运算模型下，乘法p q次，累加同阶。这是可复跑的独立参照，也直接体现正确性：每个应进入第k项的乘积恰好被访问一次。 另一种表示是多项式在足够多不同点上的值。逐点相乘很便宜；困难...

比较排序需要从比较结果中区分输入排列，因此有最坏Ω(n log n)比较次数下界。整数键还允许取位、移位和按数值寻址。利用这些操作的算法改变了模型，不能用“击败下界”来描述，也不能忽略键域和机器字长的代价。 本篇用小整数宇宙位向量实现严格前驱，再用稳定基数排序说明按位处理的成本。经典van Emde Boas结构用于解释递归缩小键域的理论方法，与16篇的静态树地址布局是不同对象。 键放进一字，不等于宇宙放进一字 设宇宙为整数集合[0,U)，当前集合有n个不同键，机器字长w位。键可以放入一字通常要求U≤2^w；若用一位表示一个宇宙元素，整个位向量放入一字却需要U≤w。两个条件相差很大。 word-RAM按字存取，指定的算术、位运算与索引按常数成本计算。若用最高置位位置直接得到前驱，还要明确提供常数时间MSB或bit-scan原语，不能只看到代码有一个函数调用就当成常数时间指令。 严格前驱定义为集合中小于x的最大键，不存在则返回空值。它不同于“小于等于x”的前驱约定。教学接口允许查询x=U以取得全体最大键；插入、删除和成员检查仍只允许0≤x<U。 一个位向量怎样实现严格前驱 令...

一维有序数组中，落在半开区间[a,b)里的键占据连续位置，两次二分就能求个数。二维点按x排序以后，一个矩形的x范围仍然连续，但其中满足y范围的点可能交错出现。把一个维度排好，没有同时解决另一个维度。 本篇先处理所有矩形查询预先给定的离线问题。扫描x时用11篇Fenwick树维护y计数，把二维条件拆成一次排序和一维动态前缀和。随后比较范围树与空间分解，说明它们为在线查询保存了哪些额外信息。 半开矩形与重复点 输入为n个整数点和q个矩形。矩形用(xlo,ylo,xhi,yhi)表示，计入满足xlo≤x<xhi且ylo≤y<yhi的点。左右或上下界倒置抛出ValueError；零宽、零高矩形返回0。重复坐标按输入中的独立点计数，空点集合法。 输出按矩形输入顺序返回计数。这里不返回点的身份列表：计数结果只有q个整数，报告查询则可能输出总计z个点引用，必须增加至少Ω(z)的写出成本。坐标比较、索引和计数加减按字长足够的RAM单位成本计算；Python大整数另有位长成本。 离线表示整个点集和查询集合在运行前已知。可以重排查询执行顺序，再用查询ID放回答案；不能据此声称同一接口支持...

17篇固定模式、扫描文本。若文本固定而查询模式不断变化，每次重新扫描长度n的文本会重复付出O(n)成本。后缀数组把文本的全部非空后缀排序，使同一模式的所有出现位置对应一个连续区间。 文本banana的后缀数组是[5,3,1,0,4,2]，依次对应a, ana, anana, banana, na, nana。查询ana得到数组中的连续两项[3,1]。结果按后缀字典序排列，不自动按文本起点递增。 固定文本的查询契约 沿用17篇Unicode码点和精确字符相等语义，不做归一化。文本长度n，查询模式长度m，命中数z。索引包含n个非空后缀；空文本的后缀数组为空。模式必须非空，否则抛出ValueError。 SuffixIndex(text).find(pattern)返回后缀数组顺序的匹配起点，保留重叠。固定文本不能原地更新：改变一个字符可能改变许多后缀的顺序，当前接口要求重新建立索引。若需要按文本位置排序，另计O(z log(z+1))时间。 后缀数组SA是起点0到n−1的一个排列，满足T[SA[r]:]按字典序递增。实现不存这些完整切片；切片只在独立的小规模参照中使用。长度为n的文本...

文本ababa中，模式aba出现在起点0和2。第一次匹配成功以后，已经读过的后缀a同时也是模式的前缀。如果把状态清零，就会漏掉第二次匹配；如果重新从每个起点比较，又重复使用了已经确定的信息。 KMP用模式的前后缀关系保存这部分信息。多个模式组成Trie以后，同一种后缀关系扩展为Aho–Corasick的失败链接。两者都让文本位置只向前移动，状态则允许回退。 输入和输出先固定 文本T长度为n，单个模式P长度为m。多模式输入是有序列表，模式数k、总长度L；重复字符串保留不同的输入ID。字符比较和数组索引先按单位成本计算，Python实现的位置是Unicode码点下标，不是UTF-8字节偏移，也不是用户可见字形编号。组合字符不自动归一化。 kmp_find(text, pattern)返回所有匹配起点，升序排列且保留重叠。空模式抛出ValueError，空文本对非空模式返回空列表。辅助函数prefix_function('')允许返回空表，这不改变匹配接口的空模式约定。 AhoCorasick(patterns).find(text)返回(起点, 模式ID)。顺序先按结束位置递增，同一...