LCA DS MST
LCA ———— Least Common Ancestors 如何计算？ 深度相同一起跳 深度不同，深度大的跳 显然，一层一层跳复杂度将会来到O(N) 空间换时间 一次多跨几步 联系：ST表 考虑保存2 的幂次级 祖先 于是我们有了一种很棒的倍增做法： 假设 y 比 x 深，则 y 需要向上跳 a = h(y) - h(x) 对 a 进行二进制拆分 令 f[x][i]为结点 x 的
Mathematical Logic 10 Halting Problem
Mathematical Logic 10 Halting Problem R-computable Let F: A* -> B* (A,B are 2 alphabets) (1)A program P computes F if for all w ∈\in∈ A*, P: w->F(w) (2)F is R-computable if there is a program w
MIT 6.006 Shortest Path Algorithm
MIT 6.006 4 Shortest Path Algorithm Overview Weighted Graph General Approaches Negative Edges Optimal Substructure Mainly 2 Algorithms： Dijkstra with O(V + E) for non-negative edge weights Bellman F
Mathematical Logic9
Before：终于和计算机相关了😭😭😭😭😭他真的，我哭死。好玩！但怀疑作业依然不会做。。。 Mathematical Logic 9 Decidability and Enumerability 可判定性 和 可枚举性 Desicion problems 判定问题 判断给定输入是否满足特定性质 i.e 设 A* 是有限字母表上的字符串集合 input : w 满足某种性质 : w ∈\i
Segment Tree
Before：Long time no see！最近强度激增，B+树de了一整天，还有MLE和TLE，感觉是某个地方写爆栈了😢数理逻辑作业还没写完，下周还要复习数分。 upd：昨天晚上过了，打算51把管理系统速通了，挑点bonus写一下（其实想全写但显然没空），弥补一下bookstore啥bonus都没写的遗憾。希望周五数分顺利！ Algorithm Of Data Structure —— S
Modern Cpp
Before：上机课偶遇modern cpp，拼劲全力无法战胜 Modern Cpp Overview！ 关于C++的刻板印象是什么？😋 笔者在学习了Java（以及相当烂的py）后，深深地感受到了C++语法规则以及一些奇奇怪怪的规定的复杂😇😇。总结一下C++： Old, out-dated, less-frequently used Unsafe （特别对，救命啊） Hard to use
Mathematical Logic 7 Completeness 1
Before：久违的数理逻辑课！上了7节课终于觉得有点入门了，还是挺有意思的。周四下午闪击南京，周五下午又闪击回来。虽然只有1天，但很开心在这短短的20个小时内帮助了不少人（都是无意间）。我要永远做个善良的人！ Mathematical Logic 7 Completeness 1 我们继续完备性的证明！ 我们知道，要证明一阶逻辑的完备性，我们只需要证明： Given a consisitent
Rust RefCell机制
Before：为什么要出一期挺莫名其妙的东西？起因还是机考，连续2次机考工程题一分没拿了（太菜了bushi），感觉对C++的各种机制很不熟悉，而Rust又是重要的一门现代编程语言。援引StanfordCS110L前言的一段话： 如果你学过 C 并接触过一些系统编程的话，应该对 C 的内存泄漏以及指针的危险有所耳闻，但 C 的底层特性以及高效仍然让它在系统级编程中无法被例如 Java 等自带垃圾收集