Zoupers的文章

第七天

0 条评论 杂类 无标签 Zoupers
不知不觉7天了，甚至开始有点想偷懒了...第13章 最短路径寻找最短路径是一个重要的问题，有着很多的应用。在一个无权图当中，最短路径的寻找可以直接使用广度优先算法。所以这一章主要讨论带权图。第一节，Bellman-Ford algorithm，我翻译不来呢^.^在有负权环图的算法中不适用，但是可以侦测负权环，用于寻找一个点到其他点的最短路径。感觉是个暴力算法，大概就是执行N-1轮算法，因为最...

第六天

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

第五天

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

第四天

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

第三天

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