1. 模拟模拟顾名思义就是题目让你做什么你就做什么考察的是将思路转化成代码的代码能力。1.2蛇形方阵方向向量比如本题⼀共四个方向分别是右、下、左、上对应(0, 1)、(1, 0)、(0, −1)、(−1, 0)// 定义 右下左上 四个⽅向 int dx[] {0, 1, 0, -1}; int dy[] {1, 0, -1, 0};「细节」考虑到位「分类讨论」模块化程序方便处理细节、调试错误2. 高精度也属于一种模拟当数据的值特别⼤各种类型都存不下的时候此时就要⽤⾼精度算法来计算加减乘除• 先⽤字符串读⼊这个数然后⽤数组逆序存储该数的每⼀位• 利⽤数组模拟加减乘除运算的过程。3. 枚举3.1 普通枚举顾名思义就是把所有情况全都罗列出来然后找出符合题⽬要求的那⼀个。因此枚举是⼀种纯暴⼒的算法。⼀般情况下枚举策略都是会超时的。此时要先根据题⽬的数据范围来判断暴⼒枚举是否可以通过。 如果不⾏的话就要⽤后⾯要学的各种算法来进⾏优化⽐如⼆分双指针前缀和与差分等。使⽤枚举策略时重点思考枚举的对象枚举什么枚举的顺序正序还是逆序以及枚举的⽅式普通枚举递归枚举⼆进制枚举。3.1.2 回⽂⽇期枚举所有⽇⽉的组合然后根据回⽂的特性推出年份然后⽐较这个数字是否在题⽬给定的区间内。寻找最优的枚举方法顺序如先枚举后判断、在指定区间内枚举、最小枚举区间3.1.3 扫雷我们发现当第⼀列中第⼀⾏的⼩格⼦的状态确定了之后其实后续⾏的状态也跟着固定下来。⽽ 第⼀列中第⼀⾏的状态要么有雷要么没有雷所以最终的答案就在0, 1, 2 中。因此我们枚举第⼀列中第⼀⾏的两种状态要么有雷要么没雷。然后依次计算剩下⾏的值看 看是否能满⾜所给的数据。寻找规律看是否有递推规律。3.2 ⼆进制枚举⼆进制枚举⽤⼀个数⼆进制表⽰中的0/1 表⽰两种状态从⽽达到枚举各种情况。• 利⽤⼆进制枚举时会⽤到⼀些位运算的知识。当每个单位枚举状态只有0/1两种状态时适合使用ACM模式与核⼼代码模式1. ACM模式 ACM模式⼀般是竞赛和笔试面试常用的模式就是只给你⼀个题目描述外加输⼊样例和输出样例 不会给你任何的代码。此时选手或者应聘者需要根据题目要求完成如下任务1. 头文件的包含2. main函数的设计3. 自己定义程序所需的变量和容器数组、哈希表等等4. 数据的输⼊根据题目叙述控制输入数据的格式5. 数据的处理各种函数接口的设计6. 数据的输出根据题目叙述控制返回数据的格式总之ACM模式相当于给你题目和⼀个空⽩的代码框让你自己设计程序来解决问题。因此ACM模式更加能够锻炼代码能力以及处理问题的整体逻辑。2. 核心代码模式 相比较于ACM模式核心代码模式就只用实现主要功能。1. 核心代码模式不需要你处理头文件、输入和输出等乱七八糟的东西只是甩给你⼀个函数接口。 你的任务就仅仅是完成这个函数2. 在这⼀个函数接口中函数头部分会传给你需要的数据直接使用即可3. 在你完成这个函数并且提交之后后台会调用你所写的函数并且根据你返回的结果测试是否正确。这种情况下我们只需完成核心的函数接口无需考虑数据的输入和输出。3.2.2 费解的开关3.2.3 Even Parity「暴力枚举」某些元素的最终状态「递推」出来其他的状态「以此类推」下去。重点在找规律4. 前缀和前缀和与差分的核⼼思想是预处理可以在暴⼒枚举的过程中快速给出查询的结果从而优化时间 复杂度。是经典的⽤空间替换时间的做法。作用快速求出数组中某一段区间的和前缀和数组性质f[i] f[i − 1] a[i]4.1 ⼀维前缀和4.3 二维前缀和前缀和矩阵f[i][j] f[i − 1][j] f[i][j − 1] − f[i − 1][j − 1] a[i][j]5. 差分前缀和与差分的核⼼思想是预处理可以在暴⼒枚举的过程中快速给出查询的结果从⽽优化时间复杂度。是经典的⽤空间替换时间的做法。学完差分之后⼤家会发现前缀和与差分是⼀对互逆的运算。作用快速对某一个区间所有元素进行统一操作。前缀和做差分可以得到原数组差分做前缀和可以得到原数组5.1一维差分差分数组的定义f[i] a[i] − a[i − 1]差分数组的性质f[i] a[i], f[i 1] − a[i]5.3 二维差分根据差分矩阵的「性质」创建差分矩阵然后根据差分矩阵的「性质」处理次q区间修改最后利⽤「前缀和」还原出来原始的矩阵。因此重点就是差分矩阵的「性质」。可以类⽐「⼀维差分数组」的性质推导出「⼆维差分矩阵」的性质• 在差分数组中某个位置标记表⽰后续元素统⼀被修改• 在差分数组中求前缀和能够还原出原始数组。由此可得差分矩阵的性质f[x1 ][y1] kf[x1 ][y2 1]− kf[x2 1][y1]− kf[x2 1][y2 1] k6. 双指针双指针算法有时候也叫尺取法或者滑动窗⼝是⼀种优化暴⼒枚举策略的⼿段• 当我们发现在两层for循环的暴⼒枚举过程中两个指针是可以不回退的此时我们就可以利⽤ 两个指针不回退的性质来优化时间复杂度。7. 二分算法当我们的解具有⼆段性时就可以使⽤⼆分算法找出答案• 根据待查找区间的中点位置分析答案会出现在哪⼀侧• 接下来舍弃⼀半的待查找区间转⽽在有答案的区间内继续使⽤⼆分算法查找结果。【⼆分问题解决流程】1. 先画图分析确定使用左端点模板还是右端点模板还是两者配合⼀起使用2. 二分出结果之后不要忘记判断结果是否存在⼆分问题细节众多⼀定要分析全⾯。查找一个元素在数组中的起始位置细节问题1.while循环里面的判断如何写while (left right)✔while (left ≤ right)✘ 死循环2.求中点的方式(left right) / 2✔①若为偶数个选中稍左边的值(left right 1) / 2✘②: 死循环若为偶数个选中稍右边的值求mid的防溢出写法mid right (left - right)/2个人理解在等于目标值的区间中选靠左的值找到目标值起点3.迭代方式因为要查找起始位置当 a[mid]t 时right移动到mid因为mid位置可能就是起始位置a[mid] t 时mid位置肯定不是目标数所以直接将left移动到mid1这种移动方式mid命中条件a[mid]tright移动到midmid求中点若选条件②选靠右边的位置会进入死循环4.整个二分结束之后整个二分结束之后需要判断是否是我们想要的结果可能查找目标根本不在数组中查找一个元素在数组中的结束位置细节问题1.while循环里面的判断如何写while (left right)✔while (left ≤ right)✘ 死循环2.求中点的方式(left right) / 2✘①: 死循环若为偶数个选中稍右边的值(left right 1) / 2✔②若为偶数个选中稍左边的值个人理解在等于目标值的区间中选靠右的值找到目标值终点3.迭代方式因为要查找起始位置当 a[mid] t 时left移动到mid因为mid位置可能就是结束位置a[mid] t 时mid位置肯定不是目标数所以直接将right移动到mid-1这种移动方式mid命中条件a[mid]tleft移动到midmid求中点若选条件①选靠左边的位置进入死循环4.整个二分结束之后整个二分结束之后需要判断是否是我们想要的结果可能查找目标根本不在数组中【STL中的二分查找】1. lower_bound 大于等于x的最小元素返回的是迭代器时间复杂度O(log N) 。2. upper_bound 大于x的最小元素返回的是迭代器。时间复杂度O(log N) 。二者均采用二分实现。但是STL中的二分查找只能适用于在有序的数组中查找如果是二分答案就不能使用。因此还是需要记忆二分模板。7.1 二分查找7.2 二分答案准确来说应该叫做「二分答案判断」。二分答案可以处理大部分「最大值最小」以及「最小值最大」的问题。如果「解空间」在从小到大的 「变化」过程中「判断」答案的结果出现「二段性」此时我们就可以「二分」这个「解空间」 通过「判断」找出最优解。7.2.1 木材加工P2440 木材加工解法一暴力枚举所有长度x表示切割出来的小段长度c表示在x的基础下最多能切出来多少段k表示最终题目需求切割的段数计算c需要枚举所有长度[ 0 , L ]每次需要遍历所有木头看x长度下每根木头n能切成多少个小段时间复杂度为O(n * L)解法二二分答案优化在解法一的基础上x所属的解空间具有二段性——在答案x的左边且出来的段数大于等于k右边小于k当 x 递增时切出来的段数 c 递减当 x 递减时切出来的段数 c 递增8. 贪⼼1. 什么是贪⼼算法贪⼼算法或者说是贪心策略企图⽤局部最优找出全局最优。1. 把解决问题的过程分成若⼲步2. 解决每⼀步时都选择当前看起来最优的解法3. 希望得到全局的最优解。2. 贪⼼算法的特点1. 对于⼤多数题⽬贪⼼策略的提出并不是很难难的是证明它是正确的。因为贪⼼算法相较于暴 ⼒枚举每⼀步并不是把所有情况都考虑进去⽽是只考虑当前看起来最优的情况。但是局部 最优并不等于全局最优所以我们必须要能严谨的证明我们的贪⼼策略是正确的。⼀般证明策略有反证法数学归纳法交换论证法等等。2. 当问题的场景不同时贪⼼的策略也会不同。因此贪⼼策略的提出是没有固定的套路和模板 的。我们后⾯讲的题⽬虽然分类但是⼤家会发现具体的策略还是相差很⼤。 因此不要妄想做⼏道贪⼼题⽬就能遇到⼀个会⼀个。有可能做完50道贪⼼题⽬之后第51道还是没有任何思路。3. 如何学习贪⼼先有⼀个认知做了⼏⼗道贪⼼的题⽬遇到⼀个新的⼜没有思路这时很正常的现象把⼼态放 平。1. 前期学习的时候重点放在各种各样的策略上把各种策略当成经验来吸收2. 在平常学习的时候我们尽可能的证明⼀下这个贪⼼策略是否正确这样有利于培养我们严谨的 思维。但是在⽐赛中能想出来⼀个策略就已经不错了如果再花费⼤量的时间去证明有点得 不偿失。这个时候如果根据贪⼼策略想出来的若⼲个边界情况都能过的话就可以尝试去写代 码了。8.1 简单贪⼼8.2 推公式如果细说的话这个专题应该叫推公式排序。其中推公式就是寻找排序规则排序就是在该排序规则 下对整个对象排序。在解决某些问题的时当我们发现最终结果需要调整每个对象的先后顺序也就是对整个对象排序 时那么我们就可以⽤推公式的⽅式得出我们的排序规则进⽽对整个对象排序。8.3 哈夫曼编码1. 树的带权路径⻓度 从树的根到任意结点的路径⻓度与该结点上权值的乘积称为该结点的带权路径⻓度。树中所有叶结 点的带权路径⻓度之和称为该树的带权路径⻓度记为其中wi 是第i 个叶结点所带的权值li 是该叶结点到根结点的路径⻓度。2. 哈夫曼树 在含有n个带权叶结点的⼆叉树中其中带权路径⻓度最⼩的⼆叉树称为哈夫曼树也称最优⼆叉 树。3. 哈夫曼算法 哈夫曼算法是哈夫曼树的构建过程是根据贪⼼策略得到的算法。主要流程为1. 初始化将所有叶⼦结点看做⼀棵棵树那么刚开始我们有⼀⽚森林2. 贪⼼每次选择根节点权值最⼩的两棵树作为左右⼦树合并成⼀棵新的⼆叉树这棵新的⼆叉树 根节点的权值为左右⼦树的权值之和3. 重复2 过程直到森林中所有的树合并成⼀棵树。在构建哈夫曼树的合并操作中就可以计算出带权路径⻓度• 在合并的过程中每⼀棵树的根节点的权值其实等于该树所有叶⼦结点的权值之和• 在每次合并的时候由于多出来两条路径此时累加上左右⼦树的根节点权值相当于计算了⼀ 次叶⼦结点到这两条路径的⻓度• 每次合并都把左右⼦树的权值累加起来就是最终的带权路径⻓度。4. 哈夫曼编码 哈夫曼编码是⼀种被⼴泛应⽤⽽且⾮常有效的数据压缩编码其构造步骤如下1. 统计待编码的序列中每⼀个字符出现的次数2. 将所有的次数当成叶结点构造哈夫曼树3. 规定哈夫曼树的左分⽀为0 右分⽀为1 那么从根节点⾛到叶⼦结点的序列就是该叶⼦结 点对应字符的编码。8.4 区间问题这种题⽬的解决⽅式⼀般就是按照区间的左端点或者是右端点排序然后在排序之后的区间上根据 题⽬要求制定出相应的贪⼼策略进⽽得到最优解。9. 倍增思想倍增顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理极⼤地优化时间复杂度。10. 离散化当题目中数据的范围很大但是数据的总量不是很大。此时如果需要用数据的值来映射数组的下标 时就可以用离散化的思想先预处理⼀下所有的数据使得每⼀个数据都映射成⼀个较小的值。之后 再用离散化之后的数去处理问题。模板一排序 去重 二分查找最常用、最标准// 离散化方式一排序 去重 二分查找 #include iostream #include algorithm using namespace std; const int N 1e5 10; int n; int a[N]; // 原始数据 int pos; // 离散化数组元素个数 int disc[N]; // 离散化专用数组 // 二分查找返回离散化后的值排序后的下标 int find(int x) { int l 1, r pos; while (l r) { int mid (l r) 1; if (disc[mid] x) r mid; else l mid 1; } return l; } int main() { cin n; for (int i 1; i n; i) { int x; cin x; a[i] x; disc[pos] x; } // 排序 去重 sort(disc 1, disc 1 pos); pos unique(disc 1, disc 1 pos) - (disc 1); // 查询每个数离散化后的值 for (int i 1; i n; i) { int x a[i]; cout x 离散化之后是 find(x) endl; } return 0; }模板二排序 STL 哈希表写法更简洁实质哈希表id用来建立映射disc数组的功能是保留大小关系// 离散化方式二排序 STL 哈希表 // 本质和方式一相同借助 STL 简化去重与查找 #include iostream #include unordered_map #include algorithm using namespace std; const int N 1e5 10; int n; int a[N]; // 原始数据 int disc[N]; // 离散化排序专用数组 int cnt; // 离散化编号 unordered_mapint, int id; // 映射原值 → 新编号 int main() { cin n; for (int i 1; i n; i) { int x; cin x; a[i] x; tmp[i] x; } // 排序 sort(disc 1, disc 1 n); // 去重 构建映射 for (int i 1; i n; i) { if (id.count(tmp[i])) continue; cnt; id[disc[i]] cnt; } // 查询每个数离散化后的值 for (int i 1; i n; i) { int x a[i]; cout x 离散化之后是 id[x] endl; } return 0; }11. 递归初阶学会从宏观的⻆度看待递归。2. 为什么会⽤到递归本质在处理主问题时需要解决⼦问题两者的处理⽅式完全⼀致。问题-相同的⼦问题-相同的⼦⼦问题......直到⼦问题不能继续拆分3. 从宏观角度看待递归1. 不要在意递归的细节展开图---写完代码不要再去纠结递归展开图2. 把递归函数当成⼀个⿊盒----赋予这个⿊盒⼀个任务3.相信这个⿊盒⼀定能帮助我们完成这个任务。4. 如何写好⼀个递归1. 先找到相同的⼦问题-确定函数的功能以及函数头的设计2. 只关⼼某⼀个⼦问题是如何解决的-函数体3. 不能继续拆分的⼦问题-递归出⼝12. 分治分治字面上的解释是「分而治之」就是把⼀个复杂的问题分成两个或更多的相同的子问题直到 最后子问题可以简单的直接求解原问题的解即子问题的解的合并。13. PSC一般在1e7的时间规模下不会超时在1e8的时间规模下会超时有时编译器在O2优化下会优化跳过一些代码导致最后评判时出现莫名其妙的bug导致WA