冷门算法杂谈

大概率省选用不到了,不过如果不退役的话,说不定有用。

Pick 定理

一个真的基本想不到去用的东西。
链接

内容

给定顶点均为整点简单多边形,Pick 定理说明了其面积(A)内部格点数目(a)边上格点数目(b)的关系:(A = a + b/2 + 1)

一般就是用来求这个的,主要瓶颈在于快速求内部格点数目和边上格点数目。

Stern-Brocot 树

这是一个可以表示出所有最简分数的数据结构。
一般用于在树上二分,因为其深度是 (O(n)) 的,所以复杂度为 (O(n)),可以用倍增去优化复杂度,不过我不是很懂。
这里给出两篇链接:

  1. Stern-Brocot Tree
  2. Stern-Brocot 树

根据这张图片去记忆吧,一般不用的真的建树,只需要了解其思想。

后记

后面可能会接着更新。

原文地址:https://www.cnblogs.com/longdie/p/lengmen.html