Category: 有趣的问题

带负权边的无向图上的最短路径问题

1月 19, 2019

路与路径从前我一直有这样一个问题：最短路取负不就变成最长路了吗？为什么最短路有这么多算法，而最长路就 NP-Hard 了呢？这是因为这里没有严格区分 trail（路或迹，可包含重复节点）和 path（路径，有时称简单路径，不包含重复节点）。我们平常所说的最短路问题是希望计 ...

problem solving 图论

7月 12, 2018

最大子数组问题：在数组找到一个连续的子数组，使该子数组的和最大。又称，最大子段和，最大子数列。算法导论上的分治算法详见课本：中文 P39，英文 P68。将 A[low..high] 分成 A[low..mid] 和 A[mid+1..high] 两份递归，并计算跨越中点的 ...

problem solving 线段树

4月 15, 2018

等。。等我有空一定来更下面是小火车某一次出题的题解 Update: 不想更了，看下面的链接吧 blog.csdn.net/joylnwang/article/details/6769160 brilliant.org/wiki/egg-dropping www.cs.um ...

DP 数学

4月 15, 2018

问题求解 Open Topic 总结注：本文所有数字都从 \(0\) 开始约瑟夫问题 \(n\) 个人 (编号为 \(0, 1, ..., n-1\)) 围成一个圈子, 从 \(0\) 号开始依次报数, 每数到第 \(m\) 个人, 这个人就得自杀, 之后从下个人开始继续报 ...

组合数学 problem solving