ALDS

虽然没啥要写的，但还是需要写一点。

Radix Sort实现

因为Radix是靠计数排序实现的，所以我们先写计数排序。

CountingSort(A[1...n]):
initialize arrays C[0,..,U-1],B[1..n]
for k = 0,..,U-1:C[k]=0
for i = 1,..,n C[key(A[i])]++
for k = 1,..,U-1: C[k]=C[k]+C[k-1] // 这里因为要前缀和，所以从1开始
for i=n,..,1:
    B[C[key(A[i])]]:=A[i]
    C[key(A[i])]--
A[1..n]:=B[1..n]

LSDRadixSort(A[1..n]):
for i=0,..,d-1:
    redefine key(x):= (x div B^i) mod B //这里是排整数，排字符串就是 x_i-'a'
    CountingSort(A)

AVL实现

//高度差取左子树减右子树
hdiff(Handle v):
    return height(v->left)-height(v->right)

rebalance(Handle v):
    if hidff(v)=2:
        w:=v->left
        if hdiff(w)=-1
            v->left:=rotateleft(w)
        return rotateright(v)
    else if hdiff(v)=-2:
        w:=v->right
        if hdiff(w)=1:
            v->right=rotateright(w)
        return rotateleft(v)
    else: return v

随机化算法

要注意一下哈希 collision 的概率证明

然后就是 cc 和 gp 的实现。

主定理

形式为 $T(n)=b\cdot T(\frac{n}{a})+\mathcal{O}(n^d\log^sn)$

然后比较 $a$ 和 $b^d$ 的关系：

1. $a<b^d$, 说明后面主导， $\mathcal{O}(n^d\log^sn)$
2. $a=b^d$, 两个部分一样， $\mathcal{O}(n^d\log^{s+1}n)$
3. $a>b^d$, 说明前面主导， $\mathcal{O}(n^{\log_b a})$

动态规划

首先 Ambitious Student 问题是优先选最晚的。