笑枕晚风の小站

参考《算法竞赛进阶指南》、AcWing题库 123456789101112131415161718192021222324252627282930313233343536class BIT {public: vector<int> c; int n; BIT() {} BIT(int n) { this->n = n; c.resize(n + 1); } BIT(vector<int> &a) { int n = a.size() + 1; c.resize(n); for (int i = 1; i <= n; ++i) { auto val = a[i - 1]; c[i] += val; if (i + lowbit(i) <= n) c[i + lowbit(i)] += c[i]; ...

参考《算法竞赛进阶指南》、AcWing题库 并查集 并查集 (Disjoint-Set) 是一种可以动态维护若干个不重叠的集合, 并支持合并与查询的数据结构。详细地说, 并查集包括如下两个基本操作: Get, 查询一个元素属于哪一个集合。 Merge, 把两个集合合并成一个大集合。 为了具体实现并查集这种数据结构, 我们首先需要定义集合的表示方法。在并查集中, 我们采用 “代表元” 法, 即为每个集合选择一个固定的元素, 作为整个集合的 “代表”。 其次, 我们需要定义归属关系的表示方法。第一种思路是维护一个数组 fff, 用 f[x]f[x]f[x] 保存元素 xxx 所在集合的 “代表”。这种方法可以快速查询元素的归属集合, 但在合并时需要修改大量元素的 fff 值, 效率很低。第二种思路是使用一个树形结构存储每个集合, 树上的每个节点都是一个元素, 树根是集合的代表元素。整个并查集实际上是一个森林 (若干棵树)。我们仍然可以维护一个数组 faf afa 来记录这个森林, 用 fa[x]f a[x]fa[x] 保存 xxx 的父节点。特别地, 令树根的 faf afa 值为 ...

参考《算法竞赛进阶指南》、AcWing题库 基本算法总结与练习 在本章中, 我们探讨了程序设计的一些基本算法思想。我们曾经多次提到过, 任何问题都有其涉及的范围, 称之为问题的 “状态空间” 。求解一个问题, 就是在这个状态空间里的遍历与映射。递推与递归是遍历状态空间的两种基本形式。本章以及接下来的章节探讨的各种算法, 则是对于 “遍历顺序” “遍历过程中的决策方法” “状态空间中各状态之间的映射方式” 给出的指导。枚举与模拟是按照问题的直接表述形式对状态空间进行朴素的遍历, 搜索则是带有一定的选择性、决策性的遍历, 贪心是在每步决策时采取局部最优策略的遍历, 动态规划则是基于全局考量的分阶段、按维度、无重复遍历。二分、倍增以及与排序相关的一些算法会对状态空间实施划分、等价、代表、拼接等手段, 直接降低遍历时需要面对的时空规模。 本章知识点 位运算 补码表示法, 理解 C++无符号、有符号整数在计算机中的存储方式 各种按位运算, 包括取位、置位、移位等, 以及一些常见技巧 快速幂, 64 位整数乘法 二进制状态压缩, 使用二进制数对状态进行压缩、提取的方法 位运算不进位的特点以及各 ...

参考《算法竞赛进阶指南》、AcWing题库 贪心 贪心是一种在每次决策时采取当前意义下最优策略的算法, 因此, 使用贪心法要求问题的整体最优性可以由局部最优性导出。贪心算法的正确性需要证明, 常见的证明手段有: 微扰 (邻项交换) 证明在任意局面下, 任何对局部最优策略的微小改变都会造成整体结果变差。经常用于以 “排序” 为贪心策略的证明。 范围缩放 证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。 决策包容性 证明在任意局面下, 作出局部最优决策以后, 在问题状态空间中的可达集合包含了作出其他任何决策后的可达集合。换言之, 这个局部最优策略提供的可能性包含其他所有策略提供的可能性。 反证法 数学归纳法 我们通过几道例题来介绍贞心算法的应用。 110. 防晒 有 CCC 头奶牛进行日光浴，第 iii 头奶牛需要 minSPF[i]minSPF[i]minSPF[i] 到 maxSPF[i]maxSPF[i]maxSPF[i] 单位强度之间的阳光。 每头奶牛在日光浴前必须涂防晒霜，防晒霜有 LLL 种，涂上第 iii 种之后，身体接收到的阳光强度就会稳定为 SPF[ ...

参考《算法竞赛进阶指南》、AcWing题库 倍增 倍增简介 倍增, 字面意思就是 “成倍增长”。这是指我们在进行递推时, 如果状态空间很大, 通常的线性递推无法满足时间与空间复杂度的要求, 那么我们可以通过成倍增长的方式, 只递推状态空间中在 2 的整数次幂位置上的值作为代表。当需要其他位置上的值时, 我们通过 “任意整数可以表示成若干个 2 的次幂项的和” 这一性质, 使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求我们递推的问题的状态空间关于 2 的次幂具有可划分性。 “倍增” 与 “二进制划分” 两个思想互相结合, 降低了求解很多问题的时间与空间复杂度。我们之前学习的快速幂其实就是 “倍增” 与 “二进制划分” 思想的一种体现。在本文中, 我们研究序列上的倍增问题, 包括求解 RMQ (区间最值) 问题的 ST 算法。关于求解最近公共祖先 (LCA) 等在树上的倍增应用, 我们将在树的直径与最近公共祖先一文中进行探讨。 倍增例题： 给定一个长度为 NNN 的数列 AAA, 然后进行若干次询问, 每次给定一个整数 TTT, 求出最大的 kkk, 满足 ∑i=1kA[i ...

参考《算法竞赛进阶指南》、AcWing题库 排序 在程序设计中, 通常会使用到以下这些排序算法, 这里把它们分为三类: 选择排序、插入排序、冒泡排序 堆排序、归并排序、快速排序 计数排序、基数排序、桶排序 前两类是基于比较的排序算法, 对 nnn 个元素进行排序时, 若元素比较大小的时间复杂度为 O(1)O(1)O(1), 则第一类排序算法的时间复杂度为 O(n2)O\left(n^{2}\right)O(n2), 第二类排序算法的时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn) 。实际上, 基于比较的排序算法的时间复杂度下界为 O(nlog⁡n)O(n \log n)O(nlogn), 因此堆排序、归并排序与快速排序已经是时间复杂度最优的基于比较的排序算法。 第三类算法换了一种思路, 它们不直接比较大小, 而是对被排序的数值采取按位划分、分类映射等处理方式, 其时间复杂度不仅与 nnn 有关, 还与数值的大小范围 mmm 有关。 离散化 排序算法的第一个应用是离散化。通俗地讲, “离散化” 就是把无穷大集合中的若干个元素映射为有限集合以便于统计的方法。例 ...

参考《算法竞赛进阶指南》、AcWing题库 二分 二分法是一种随处可见却非常精妙的算法, 经常能为我们打开解答问题的突破口。 二分的基础的用法是在单调序列或单调函数中进行查找。因此当问题的答案具有单调性时, 就可以通过二分把求解转化为判定 (根据复杂度理论, 判定的难度小于求解), 这使得二分的运用范围变得很广泛。进一步地, 我们还可以扩展到通过三分法去解决单峰函数的极值以及相关问题。 据说, 只有 10%10 \%10% 的程序员能写对二分。二分的实现方法多种多样, 但是其细节之处确实需要仔细考虑。对于整数域上的二分, 需要注意终止边界、左右区间取舍时的开闭情况, 避免漏掉答案或造成死循环; 对于实数域上的二分, 需要注意精度问题。 整数集合上的二分 本文所使用的二分的写法保证最终答案处于闭区间 [l,r][l, r][l,r] 以内, 循环以 l=rl=rl=r 结束, 每次二分的中间值 mid 会归属于左半段与右半段二者之一。 在单调递增序列 aaa 中查找 ≥x\geq x≥x 的数中最小的一个 (即 xxx 或 xxx 的后继): 123456while (l < ...

参考《算法竞赛进阶指南》、AcWing题库 前缀和与差分 前缀和 对于一个给定的数列 AAA, 它的前缀和数列 SSS 是通过递推能求出的基本信息之一: S[i]=∑j=1iA[j]S[i]=\sum_{j=1}^{i} A[j] S[i]=j=1∑i​A[j] 一个部分和, 即数列 AAA 某个下标区间内的数的和, 可表示为前缀和相减的形式: sum⁡(l,r)=∑i=1rA[i]=S[r]−S[l−1]\operatorname{sum}(l, r)=\sum_{i=1}^{r} A[i]=S[r]-S[l-1] sum(l,r)=i=1∑r​A[i]=S[r]−S[l−1] 在二维数组 (矩阵) 中, 可类似地求出二维前缀和, 进一步计算出二维部分和。 99. 激光炸弹 地图上有 NNN 个目标，用整数 Xi,YiX_{i}, Y_{i}Xi​,Yi​ 表示目标在地图上的位置，每个目标都有一个价值 WiW_iWi​。 注意：不同目标可能在同一位置。 现在有一种新型的激光炸弹，可以摧毁一个包含 R×RR \times RR×R 个位置的正方形内的所有目标。 激光炸弹的投放是通 ...

参考《算法竞赛进阶指南》、AcWing题库 递推与递归 一个实际问题的各种可能情况构成的集合通常称为 “状态空间”, 而程序的运行则是对于状态空间的遍历, 算法和数据结构则通过划分、归纳、提取、抽象来帮助提高程序遍历状态空间的效率。递推和递归就是程序遍历状态空间的两种基本方式。 递推与递归的宏观描述 对于一个待求解的问题, 当它局限在某处边界、某个小范围或者某种特殊情形下时, 其答案往往是已知的。如果能够将该解答的应用场景扩大到原问题的状态空间, 并且扩展过程的每个步骤具有相似性, 就可以考虑使用递推或者递归求解。 以已知的 “问题边界” 为起点向 “原问题” 正向推导的扩展方式就是递推。然而在很多时候, 推导的路线难以确定, 这时以 “原问题” 为起点尝试寻找把状态空问缩小到已知的 “问题边界” 的路线, 再通过该路线反向回溯的遍历方式就是递归。我们通过两幅图来表示递推与递归的差别。 我们刚才也提到, 使用递推或递归要求 “原问题” 与 “问题边界” 之间的每个变换步骤具有相似性, 这样我们才能够设计一段程序实现这个步骤, 将其重复作用于问题之中。换句话说, 程序在每个步骤上应 ...

参考《算法竞赛进阶指南》、AcWing题库 位运算 bit 是度量信息的单位, 包含 0 和 1 两种状态。计算机的各种运算最后无不归结为 一个个 bit 的变化。熟练掌握并利用位运算, 能够帮助我们理解程序运行中的种种表现, 提高程序运行的时空效率, 降低编程复杂度。 在 C++\mathrm{C}++C++ 中, 8 位二进制数对应 char 类型, 范围 为 −128∼127-128 \sim 127−128∼127, 其中 0×FF0 \times F F0×FF 代表一1, 0×7F0 \times 7 F0×7F 代表最大值 127 。 在阅读本节之前, 读者应该对以下算术位运算有一个初步的认识: 与 或 非 异或 and,&and,\&and,& $or, $ not,∼not,\simnot,∼ 它们不局限于逻辑运算, 均可作用于二进制整数。为了避免混淆, 统一用单词 xor 表示异或运算, 而用符号 “^” 表示乘方运算 (虽然该符号在 C++中表示异或)。 另外, 在 mmm 位二进制数中, 为方便起见, 通常称最低位 ...