杂类

第六天

0 条评论 杂类 无标签 Zoupers
第二部分 图算法（Graph algorithms） 经历了五天摸鱼，终于摸到了图算法，希望能够摸到一点尾巴... 第11章 图的基础（Basics of graphs） 说实话，感觉英文比中文好理解，不知道为什么，可能是这些单词接触多了... 许多编程问题都可以被建模为一个图问题，然后通过适当的图算法就可以得到解决。一个典型的图就是国家的道路和城市，然而有些时候图深深的藏在问题之中，而...

第五天

0 条评论 杂类 无标签 Zoupers
突然难度就提升了，还好都能懂，不然今天写不动了-.- 区间查询（Range queries） 区间查询是一种给定一组数据，查找这个数组的一个子数组的某些性质的问题，比如查询子数组的和、最小值、最大值。 第一节首先介绍了静态查询，这是一种离线算法，可以通过构造前缀和数组来完成常数时间的子数组和查询。但是针对最小值（最大值）的查询，则是构建了一个记录数组，这个构造呢...还是看书吧，这个思想...

第四天

0 条评论 杂类 无标签 Zoupers
第七章 动态规划（Dynamic programming） 吼吼吼吼 动态规划是一种结合了完全搜索（complete search）和贪心算法优点的技术。动态规划可以用于解决那些可以划分为局部重合的子问题的问题（可能有点抽象，但是结合作者提供的题会好一点）。 作者说学会理解动态规划是每一个编程竞赛选手职业生涯的里程碑。我也觉得，哈哈。 第一节，还是硬币问题，是时候真正的AC这道题了。这里...

第三天

0 条评论 杂类 无标签 Zoupers
第五章 完全搜索（Complete search） 又不知道怎么翻译了，所以还是把原词放着… 首先介绍了一下完全搜索是一种基本上能够解决所有算法问题的方法。主要思想就是遍历整个解空间来寻找问题的答案。 第一节讲了如何生成子集，也就是我们如何得到一个集合的幂集，给了两个实现方案。一个是递归的实现，一个是迭代的实现。 第二节讲了如何生成全排列。也讲了两种方法，第一种递归和生成子集的递归算法差...

第二天

0 条评论 杂类 无标签 Zoupers
简述 第三章 排序 章节开头先说明了排序在算法中的作用和地位。排序是非常多问题的子问题，所以排序算法很基础。 第一节通过给出排序的基本问题来引入了排序的算法，首先介绍的是最简单的时间复杂度为O(n^2)的冒泡算法，然后通过对冒泡算法的解析抛出了逆序这个概念，然后通过针对冒泡算法必须在相邻的元素之间进行排序的需求抛出了归并排序。不过并没有给出归并时合并的具体算法。然后提出了一个问题就是基于这种...