如何在图中新增一条边,使任意两点的距离之和最小?

游戏《太阳帝国的原罪》里,瓦萨里种族可以建造相位跳跃稳定器,飞船可以直接从一个有相位跳跃稳定器的星球跳跃到另一个有相位跳跃稳定器的星球,无需现有路线。

如图1,粉色是我的星球。如何添加两个相位跳跃稳定器,能够最大程度地减少我方飞船在各个星球之间的飞行距离?

把上图数学化,如图2,[……]

继续阅读

Manacher最长回文算法

本文将一步一步构造Manacher算法,心急的一定看不懂!请先练习下面的习题。

探索最长回文串性质

题1:已知字符串以center为中心对称,求完整的字符串。

abcd???
   |
center

abcdcba
   |
center

题2:接上题,a[……]

继续阅读