~ Esoteria Algorithm in Reverse Observatory

错排问题及其递推式和通项公式

Prologue

  在组合数学中, 一个 错排 是一个集合中的元素都不出现在自己原来的位置的序列。换言之,一个错排是一个没有定点的序列。这样的序列的个数称为 错排数,记作 DnD_n

Cover Image

JavaScript 中的 Lambda 演算

序幕

判定性问题和可计算性

在形式化语言中,如何有效地接收并且验证一个命题的正确性?

邱奇 - 图灵猜想

邱奇 - 图灵猜想是一个关于可计算性理论的假设。该假设论述了关于函数特性的,可有效计算的函数值。简单来说,邱奇 - 图灵猜想认为「任何在算法上可计算的问题同样可由图灵机计算」。

Cover Image

ZTE Quartz ZW10 劝退指南

Prologue

Wear OS by Google
Make every minute matter

服役 3 年的某 iwownfit 基本挂了,于是考虑捡一个 Wear OS[1] 洋垃圾 (除了看时间其他都是伪需求)

Cover Image

Manjaro To Go | 装进口袋的 Manjaro

Prologue

Windows To Go[1] 类似, Manjaro To Go 就是将 Manjaro 安装到电脑上 USB 连接的外部驱动器,并且能在不同的平台上启动。

幼儿园数学

CAUTION
This pointless post is intended for childern under six.

To begin with,watch this video.

FHQ Treap | 非旋式树堆

Prologue

前置技能

一些定义

  • 树中任意节点的权值都大于或等于其父节点的权值,则称该二叉树满足 “小根堆性质”
  • 二元搜寻树(Binary Search Tree, BST)是一棵空树或具有下列性质的二叉树

左偏树

Prologue

左偏树是一种合并复杂度很优秀的堆。下图就是一棵典型的左偏树,蓝色的数字为该节点的路径长。

线段树优化 Dijkstra

过早的优化是万恶之源。
Go beyond speed.

一般的 Dijkstra 使用 priority_queue 维护当前最短路的距离,但不吸氧气的 STL 性能表象不佳。维护当前最短路距离需要不断取出最小值,可以通过线段树查询最小值再修改为无穷大来模拟。

负环与单源最短路计数

Prologue

  • 若图上存在一个环,环上各边的权值之和是负数,则称这个环是负环。

负环判定

​设 cnt[v] 表示从 11vv 的最短路径包含的边数,cnt[1]=0。当执行更新 d[v]=d[u]+w 时,同样更新 cnt[v]=cnt[u]+1。此时若发现 cnt[v]>=n,则图中有负环。若算法正常结束,则图中没有负环。