头像

回归线




离线:1天前



单处理器上的单位时间任务最优调度问题

使用提前优先形式(early-first form)
提前(early)的任务都置于延迟(late)的任务之前,提前任务按截止时间单调递增的顺序排列。

原问题可以归结为寻找提前任务子集$A$的问题。确定$A$之后,将$A$中元素按截止时间递增的顺序排列,然后将延迟任务$S-A$以任意顺序排列其后。

定义 $N_t(A)$ 表示 $A$ 中截止时间小于等于 $t$ 的任务数。则 $N_0(A)=0$

对任意任务集合 $A$,下面性质是等价的:
1. $A$ 是独立的
2. 对 $t=0,1,2,\cdots,n$ 有 $N_t(A)\le t$
3. 如果 $A$ 中任务按截止时间单调递增的顺序调度,那么不会有任务延迟

最小化延迟任务的惩罚之和 $\iff$ 最大化提前任务的惩罚之和

解法1

$O(n^2)$

  1. $A=\emptyset$
  2. 把任务按照惩罚值单调递减的顺序排列。
  3. 从前到后考虑每个任务,需要满足任务加入 $A$ 后,满足 $N_t(A)\le t$

解法2

$O(n\alpha(n))$ 使用并查集

  1. 初始化 $n$ 个时间槽为空
  2. 把任务按照惩罚值单调递减的顺序排列
  3. 从前到后处理每个任务,当处理任务 $a_j$ 时,如果存在不晚于 $a_j$ 的截止时间 $d_j$ 的空的时间槽,则将 $a_j$ 分配到其中最晚的那个。如果不存在这样的时间槽,将 $a_j$ 分配到最晚的空时间槽

最小平均完成时间调度问题

按照任务处理时间单调递增的顺序调度

离线缓存最小化缓存未命中(cache miss)次数

将来最远(furthest-in-future)的贪心策略。
逐出缓存的数据的方法:选择在请求序列中,下一次访问距离最远的数据




回归线
11天前

$$P(n) = \begin{cases}
1 & n=1 \newline
\sum_{k=1}^{n-1} P(k)P(n-k) & n \ge 2
\end{cases}$$
卡塔兰数 (Catalan number) 的递推公式与此类似。

涉及这种的的 DP,采用 带备忘的自顶向下法 (top-down with memoization),比自底向上法 (bottom-up method) 的时间复杂度更低。参见习题15.3-1的证明。(不考虑爆栈和递归调用的开销)

$tD/eD$ 动态规划算法

如果一个动态规划算法的表格大小为 $O(n^t)$ 的,每个表项依赖其他的 $O(n^e)$ 个表项,则称这是一个 $tD/eD$ 动态规划算法

矩阵链乘法是 $2D/1D$
最长公共子序列 (LCS) 是 $2D/0D$




回归线
12天前

最小生成树 (minimum spanning tree, MST)
1. 有 $|V| - 1$ 条边
2. 没有环
3. 可能不唯一

Kruskal

使用并查集

时间复杂度

使用并查集时,总时间复杂度
$$O((V+E)\alpha(V))\tag{1}$$
因为 $| E | \ge | V | - 1$, 所以公式1变为
$$O(E\alpha(V))\tag{2}$$
因为 $\alpha(V)=O(\log V)=O(\log E)$,所以公式2变为
$$O(E\log E)\tag{3}$$
由于 $| E | \lt |V|^2$,所以 $\log |E| = O(\log V)$, 所以时间复杂度可以写为
$$O(E\log V)$$

kruskal.png

Prim

时间复杂度

使用邻接表,时间复杂度可以为 $O(E\log V)$
使用邻接矩阵,时间复杂度为 $O(V^2)$

邻接表

邻接表长度之和为 $2|E|$

使用最小堆

$O(V\log V + 2E\log V) = O(V\log V + E\log V) = O(E\log V)$

使用Fibonacci 堆

$O(V\log V + 2E) = O(E + V\log V )$

边比较稀疏的时候,两种优先队列的时间复杂度差不多
边比较稠密的时候,Fibonacci 堆比 最小堆 快

prim.png

推论

$G$ 可能有多个最小生成树,对每个树中的边的权重排序,所得的权重排序列表完全相同



分享 tmp-FFT

回归线
13天前

DFT 用于将时域信号转换为频域信号。也可以看成对时域信号的求值 (evaluation)

IDFT 用于将频域信号转换为时域信号。也可以看成是对频域信号的插值 (interpolation)

递归版 FFT

recursive-fft.png

迭代版 FFT

iterative-fft.png

bit_reverse_copy.png

rev(k)k 的 $\log_2 n$ 位二进制数的翻转后的数字




回归线
14天前

线段的性质

使用叉积 (cross product) 来计算线段的性质
$$p_1 \times p_2 = \det\left[\begin{matrix}
x_1 & x_2 \newline
y_1 & y_2
\end{matrix}\right] = x_1y_2-x_2y_1 = -p_2 \times p_1$$
正负号满足右手定则,绝对值是两个向量组成的平行四边形的面积。
如果叉积为 $0$,说明两个向量共线性,即方向相同或相反。

1.png

同起点有向线段的方向

两个有向线段 $\overrightarrow{p_0p_1}$ 和 $\overrightarrow{p_0p_2}$。
如果 $(p_1 - p_0) \times (p_2 - p_0)$ 为 ,则 $\overrightarrow{p_0p_1}$ 需要 逆时针 旋转,才能转到 $\overrightarrow{p_0p_2}$。
如果为 ,则 $\overrightarrow{p_0p_1}$ 需要 顺时针 旋转,才能转到 $\overrightarrow{p_0p_2}$

double cross_product(const Point& p0, const Point& p1, const Point& p3) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

连续线段的是左转还是右转

两个有向线段 $\overrightarrow{p_0p_1}$ 和 $\overrightarrow{p_1p_2}$ 在 $p_1$ 处的转向,即 $\angle{p_0p_1p_2}$ 的转向。
可以通过计算 $\overrightarrow{p_0p_1}$ 和 $\overrightarrow{p_0p_2}$ 的转向来判断

如果 $(p_1 - p_0) \times (p_2 - p_0)$ 为 ,则在 $p_1$ 处 左转。如果为 ,在 $p_1$ 处则 右转

两条线段相交

两条线段相交 $\iff$ 下面两个条件至少有一个成立:
1. 每条线段都跨越了另一条线段所在的直线
2. 一条线段的某个端点落在另一条线段上

判断线段 $\overrightarrow{p_1p_2}$ 和 $\overrightarrow{p_3p_4}$ 相交, 调用 segments_intersect(p1, p2, p3, p4)

bool on_segment(const Point& p1, const Point& p2, const Point& p3) {
    // 判断 点 p3 是否在 线段 p1p2 上,应该满足两个条件:
    //     1. (p2 - p1) \times (p3 - p1) 为 0
    //     2. p3 在 p1p2 为对角线的矩形内
    // 在这里,被调用时,`segments_intersect` 的判断条件已经保证了第一条满足条件,只需要判断第二条

    // min(x1, x2) < = x3 <= max(x1, x2) && min(y1, y2) < = y3 <= max(y1, y2)
    return (p1.x - p3.x) * (p2.x - p3.x) <= 0 &&  (p1.y - p3.y) * (p2.y - p3.y) <= 0;
}

bool segments_intersect(const Point& p1, const Point& p2, const Point& p3, const Point& p4) {
    const double d1 = cross_product(p3, p4, p1);
    const double d2 = cross_product(p3, p4, p2);
    const double d3 = cross_product(p1, p2, p3);
    const double d4 = cross_product(p1, p2, p4);

    if (d1 * d2 < 0 && d3 * d4 < 0) {
        return true;
    }

    if (std::abs(d1) < eps) {
        return on_segment(p3, p4, p1);
    }

    if (std::abs(d2) < eps) {
        return on_segment(p3, p4, p2);
    }

    if (std::abs(d3) < eps) {
        return on_segment(p1, p2, p3);
    }

    if (std::abs(d4) < eps) {
        return on_segment(p1, p2, p4);
    }

    return false;
}

线段集合中是否存在两条线段相交

$O(n\log n)$

Shamos–Hoey algorithm
对 $2n$ 个线段端点的排序,通常按照 $(x, e, y)$ 来对端点按照字典序排序。
其中 $x$ 和 $y$ 为端点的坐标,$e = 0$ 表示左端点,$e=1$表示右端点。
对垂直线段也适用:上述排序会将底部端点当做左端点,顶部端点当做右端点 (参见习题 33.2-9)

any_seg_int.png

Bentley–Ottmann algorithm 对其做了改进?(wikipedia )

凸包

$n$ 为总点数, $h$ 为 凸包上的点的数目

Graham Scan

$O(n\log n)$
graham_scan.png

Jarvis’s march

$O(nh)$

incremental method

$O(n\log n)$

we first sort the points from left to right, yielding a sequence $\langle p_1, p_2,\cdots,p_n\rangle$. At the ith stage, we update the convex hull of the $i - 1$ leftmost points, $CH\left({ p_1, p_2,\cdots, p_{i-1}}\right)$, according to the ith point from the left, thus forming $CH\left({ p_1, p_2,\cdots, p_{i}}\right)$. Exercise 33.3-6 asks you how to implement this method to take a total of $O(n\log n)$ time.

divide-and-conquer method

$O(n\log n)$

we divide the set of n points in $\Theta(n)$time into two subsets, one containing the leftmost $\lceil \frac{n}{2}\rceil$ points and one containing the rightmost $\lfloor \frac{n}{2}\rfloor$ points, recursively compute the convex hulls of the subsets, and then, by means of a clever method, combine the hulls in $$O(n)$ time. The running time is described by the familiar recurrence $T(n) = 2T(\frac{n}{2} + O(n)$, and so the divide-and-conquer method runs in $O(n\log n)$ time.

prune-and-search method

$O(n\log h)$

With this method, we find the upper portion (or “upper chain”) of the convex hull by repeatedly throwing out a constant fraction of the remaining points until only the upper chain of the convex hull remains. We then do the same for the lower chain. This method is asymptotically the fastest




回归线
15天前

把 $n$ 个球 放入 $b$ 个不同的盒子中,$n \ge b$

  1. 假设 $n$ 个球是不同的,且不考虑它们在盒子中的顺序 $b^n$
  2. 假设 $n$ 个球是不同的,且它们在盒子中的有序 $A(b + n - 1, n)$
  3. 假设 $n$ 个球是相同的,因而它们在盒子中的顺序不重要 $\binom{b + n - 1}{n}$
  4. 假设 $n$ 个球是相同的, 且盒子不能为空 $\binom{n - 1}{b - 1}$



回归线
15天前

计数

全排列

$$P(n, k) = \frac{n!}{(n-k)!}$$

组合

$$\binom{n}{k} = \frac{P(n, k)}{P(k, k)} = \frac{n!}{k!(n-k)!}$$

$$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}\qquad \text{for } 0 \lt k \le n$$
$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$
$$\binom{n}{k} = \binom{n}{n-k}$$
$$\left(x+y\right)^n = \sum_{k=0}^{n}\binom{n}{k}x^ky^{n-k}$$
$$\sum_{k=0}^{n}\binom{n}{k} = 2^n$$
$$\sum_{k=0}^{n}\binom{n}{k}k = n2^{n-1}$$

伯努利实验

伯努利实验的成功概率为 $p$,失败概率为 $q = 1-p$

几何分布

一系列伯努利实验,定义随机变量 $X$ 为获得一次成功所需的实验次数,则
$$Pr\left(X=k\right) = q^{k-1}p$$

$$E\left[X\right] = \sum_{k=1}^{\infty}kq^{k-1}p = \frac{p}{q}\sum_{k=0}^{\infty}kq^k=\frac{p}{q}\frac{q}{(1-q)^2}=\frac{1}{p}$$

$$Var\left[X\right] = \frac{q}{p^2}$$

二项分布

一系列伯努利实验,定义随机变量 $X$ 为 $n$ 次实验中成功的次数, 则 $$Pr\left(X=k\right)=\binom{n}{k}p^kq^{n-k}=b(k;n,p)$$

$$E\left[X\right] = np$$

$$Var\left[X\right] = npq$$




回归线
16天前

容斥原理 (principle of inclusion and exclusion)

\begin{aligned}
| A_1 \cup A_2 \cup \cdots \cup A_n | = \newline
&| A_1 | + | A_2 | + \cdots + | A_n | &\newline
&- | A_1 \cap A_2 | - | A_1 \cap A_3 | - \cdots \quad &\text{(all pairs)} \newline
&+ | A_1 \cap A_2 \cap A_3 | + \cdots \quad &\text{(all triples)} \newline
&\qquad\qquad\vdots &\newline
+ &(-1)^{n-1} | A_1 \cap A_2 \cap \cdots \cap A_n |&
\end{aligned}

握手定理 (handshaking lemma)

如果 $G = \left(V, E\right)$ 是一个无向图,则
$$\sum_{v \in V} degree(v) = 2 | E |$$

超图 (hypergraph)

超图的超边,连接的不是两个顶点,而是任意顶点子集。

超图可以用二分图来表示,其中,超图的顶点集是二分图的一个顶点集,超图的超边集是二分图的另一个顶点集。如果超图的顶点在某条超边内,二分图的两部分顶点也对应的连接起来。

连通无向图的点边的关系

任意连通无向图 $G=\left(V, E\right)$ , 满足 $|E| \ge |V| - 1$

树是连通、无环的无向图

二叉树

非空的二叉树中,2 度的结点树比叶结点少 $1$

满二叉树 (full binary tree)

320px-Full_binary.svg.png
除叶结点之外,每个结点都有两个孩子的二叉树,称为满二叉树

满二叉树中内部结点数目比叶结点少 $1$

如果把内部结点和叶结点不做区分都看成是结点时,可以这样认为:
如果一个二叉树,没有任何一个结点只有一个孩子,则它是满二叉树

内路径长度、外路径长度 (internal path length/external path length)

对于一个满二叉树内路径长度 $i$ 是所有内部结点深度之和,外路径长度 $e$ 是所有叶结点深度之和。

对一个有 $n$ 个内部结点的满二叉树,有 $e = i + 2n$

完全 $k$ 叉树 (complete k-ary tree)

complete_binary_tree.png
如果 $k$ 叉树的所有叶结点深度相同,并且所有内部结点的度数为 $k$,则称为完全 $k$ 叉树

图染色

树的色数为 $2$

下列三条等价:
1. $G$ 是二分图
2. $G$ 的色数为 $2$
3. $G$ 没有长度为奇数的环




回归线
17天前



回归线
17天前
#include <iostream>
#include <map>

int main() {
    int n;
    std::cin >> n;

    std::map<int, int> m;
    int s;

    while (n--) {
        std::cin >> s;
        ++m[s];
    }

    int cnt = 0;
    int res = 0;
    for (auto [k, v] : m) {
        if (v > cnt) {
            cnt = v;
            res = k;
        }
    }

    std::cout << res << std::endl;

    return 0;
}