zhangxixi的博客

Haskell Study Note 8 | Higher-Order Function Functions as Values We can use functions as variables, parameters and so on. An example is (function as values) : 12345addOne :: Int -> IntaddOne x = x + 1f :: Int -> Intf = addOne In this case, function f is the same as funtion addone. Another e...

Haskell Study Note 7 : Tuple Tuple Tuple can have different types of values. Common form : (String, Int)、(Bool, Double, String) like : ("Alice", 20) Pair & Triple : 12345-- Pair("Alice", 20)-- Triple("Bob", 25, "Engineer") Basic operations of a Tu...

高等数学启蒙 微分 f′(x)=dydxf'(x)=\dfrac {dy}{dx}f′(x)=dxdy​ 积：d(uv)dx=dudxv+dvdxu\dfrac{d(uv)}{dx}=\dfrac{du}{dx}v+\dfrac {dv}{dx}udxd(uv)​=dxdu​v+dxdv​u，即： d(uv)=du⋅v+dv⋅ud(uv)=du\cdot v+dv\cdot ud(uv)=du⋅v+dv⋅u 商同理： 不定积分 F(x)=∫f(x)dxF(x)=\int f(x)dxF(x)=∫f(x)dx，则 f(x)f(x)f(x) 的原函数是 F(x)F(x...

Haskell Study Note Lesson 6 : Recursion There are two types of recursion : Nested Recursion Pattern Matching A typical recursion is like : 123factorial :: Integer -> Integerfactorial 0 = 1factorial n = n * factorial (n - 1) The end of a recursion is called Base Case. Practice : Multiplicati...

字符串进阶算法 1 ：exKMP、SA、SAM、后缀平衡树 exKMP / Z函数 对于字符串 sss 的每个后缀，求其与 sss 的最长公共前缀 ziz_izi​ 要求 O(n)O(n)O(n) 我们考虑当前在对 iii 进行操作。 之前已经有一段区间 [l,r][l,r][l,r] 满足 s[1,r−l+1]=s[l,r]s[1,r-l+1]=s[l, r]s[1,r−l+1]=s[l,r]，且 rrr 最大。 若 i≤ri\le ri≤r，则直接继承 zi=zi−l+1z_i=z_{i - l + 1}zi​=zi−l+1​ 接下来暴力匹配，只要匹配成功，此时 rrr...

一些动态规划的优化算法：斜率优化、四边形不等式、Slope Trick、wqs二分 斜率优化 考虑我们求解的问题可以简化为： fi=min⁡(fj−j×ai)f_i=\min(f_j-j\times a_i) fi​=min(fj​−j×ai​) 令 fi=b,fj=y,ai=kf_i=b,f_j=y,a_i=kfi​=b,fj​=y,ai​=k，则： b=y−kx⇒y=kx+bb=y-kx\\ \Rightarrow y = kx + b b=y−kx⇒y=kx+b 其中 (x,y)(x,y)(x,y) 是本来就有的点（而且有很多个，均为备选项），bbb 为我们要求的东西，我们希望 b...

一些高级搜索优化技巧 A* 我们考虑bfs+优先队列优化寻找最短路的过程。 我们有三类点（本质是状态）： 当前已经确定点（1） 队列中的点（2） 还未探索过的点（3） 初始时起始点在1类点，终止点为3类点。当终止点变成1类点时，我们就可以直接结束。 我们考虑会优先把哪个2类点丢到1类点中：假设当前到某个2类点的最优是（已走路径长度） f(i)f(i)f(i)，我们会选择**f(i)f(i)f(i) 最小的点**进行下一步。 以上是我们传统的做法，接下来介绍 A* 我们考虑我们增加一个预测函数 g(i)g(i)g(i)，代表从 iii 号点到终点预估需要的代价是 g(i)g(i)g(...

平衡树全家桶 2 笛卡尔树 仅支持静态，不支持动态 建树过程：单调栈。对于每个新加入的点 xxx 最后pop掉的点 yyy，则 yyy 是 xxx 左子树 最后pop不走的点 zzz，则 xxx 是 zzz 右子树 用于静态区间最大值之类的维护 Size Balanced Tree 树的性质：叔叔比侄子大，即： 1234size(N.left) >= size(N.right.left)size(N.left) >= size(N.right.right)size(N.right) >= size(N.left.left)size(N.right) >= s...

平衡树全家桶 1 Treap Treap = Tree（BST）+ Heap 左旋 右旋 这两个显然，推一推就行 我们对每个节点附一个随机权值，用于维护小根堆/大根堆 每次，先修改（按照二叉搜索树的方式），然后转转转，使其符合堆 FHQ-Treap 无旋Treap 同样有BST和Heap的性质。（只要是Treap，其随机权值就给了其深度为log的保证） 我们有两种操作： spilt(root, val) 按照val划分 如果当前点 <= val，则 split(R, val)，并把得到的其中一棵树连为根节点的新右子树 如果当前点 > val，则 split(L, v...

Haskell Study Note Lesson 5 List Creating Lists Note : type homogeneous [1,2,3] [1..5]、[2,4..10] Accessing List Elements index from 0 !!：list !! index A safe way : 1safeIndex xs i = if i < lenght xs then Just(xs !! i) else Nothing Concatenation & Extension Concatenation : ++ like [1, ...