题意：在图上找一条从 $1$ 到 $n$ 的路径，是路径上选出两个点 $p,q$（满足 $p$ 在 $q$ 之前），使得节点 $q$ 的权值减去节点 $p$ 的权值最大。

在原图上用 $SPFA$ 或 $Dijkstra$ 求出数组 $D$，从 $1$ 出发，$D[x]$ 代表经过 $x$ 点时，已经过路径上最小的点权是多少；同理，建立一个反图，从 $n$ 出发，求出数组 $F$，$F[x]$ 代表经过 $x$ 点时，已经过路径上最大的点权是多少。数组的计算与单源最短路径的计算类似，如下：

题意：给定一棵 $N$ 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树，求增加的边的权值总和最小是多少。

把每条边按权值从小到大排序，扫描每条边，执行 $Kruskal$ 算法。

设扫描到的边为 $(x,y,z)$ ，$x$ 所在集合为 $S_x$ ，$y$ 所在集合为 $S_y$ ，那么应该合并 $S_x$ 与 $S_y$ 。但是由于我们要在两个集合之间增加若干条边，由于要使最小生成树不变，且增加的权值最小，所以增加边的权值应该为 $z+1$ 。两个集合之间除了最小生成树那条边，还可以连接 $|S_x|\times|S_y|-1$ 条边，所以把 $(z+1)\times (|S_x|\times|S_y|-1)$ 累加到答案中即可求解。

两种解法。

解法一：分层图

用 $dis[i][j]$ 代表到达第 $i$ 个基站，已经使 $j$ 条电缆免费时，所经过的路径上最贵的电缆的花费。

设存在一条从 $from$ 到 $i$ 的边，权值为 $num$ ，于是可以很快推出转移方程：

$$dis[i][j]=max(dis[from][j],num)$$

$$dis[i][j+1]=dis[from][j]$$

A. Chips Moving

题意：有一个 $n$ 个数的数列，第 $i$ 个数的位置是 $x_i$，有些数可能放在相同的位置。你可以对每个数做以下两种操作：

1. 将第 $i$ 个数向左或向右移动 $2$ 个位置(即用 $x_i-2$ 或 $x_i+2$ 替换当前坐标 $x_i$)；
2. 将第 $i$ 个数向左或向右移动 $1$ 个位置(即用 $x_i-1$ 或 $x_i+1$ 替换当前坐标 $x_i$)，花费 $1$ 个硬币。

A. Circle of Students

题意：有 $n$ 个学生围成一圈，他们各自的编号不同，从 $1\sim n$ ，只有当他们的编号从小到大顺时针或逆时针围成一个圈时，他们才能开始舞会。

给出学生的排列顺序，判断他们能否立即开始舞会。

输入：第一行一个数，$q$，代表问题个数；对于每一个问题，第一行一个数，$n$，代表学生个数；第二行 $n$ 个数，代表学生的排列顺序。

A. Hotelier

题意：一个长度为 $10$ 的序列，编号为 $0\sim 9$ ，给定一个操作序列，包含三种操作方式：

1. 使序列最左边为 $0$ 的位置变为 $1$；
2. 使序列最右边为 $0$ 的位置变为 $1$；
3. 指定一个位置，使其变为 $0$。

求操作后的序列。

输入：第一行一个整数，$n$，代表操作序列长度；第二行一个操作序列。

A. Important Exam

题意：有 $n$ 个学生和 $m$ 个问题，给出每个学生的答案和每个问题的分值，求出最可能的所有学生总分。

输入：第一行，$n$ 和 $m$；第 $2\sim n+1$ 行，每行一个字符串，代表每个学生的答案；最后一行 $m$ 个数，代表每个问题的分值。

输出：一个数，最可能的学生总分。

题意：本题中，我们将用符号 $\lfloor c \rfloor$ 表示对 $c$ 向下取整，例如：$\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。

蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

题意：给定一个 $1\sim n$ 的排列 $p_1,p_2,…,p_n$，可进行若干次操作，每次选择两个整数 $x,y$，交换 $p_x,p_y$。

设把 $p_1,p_2,…,p_n$ 变成单调递增的排列 $1,2,…,n$ 至少需要 $m$ 次交换。

求有多少种操作方法可以只用 $m$ 次交换达到上述目标。

题意：给定一个正整数 $L$，$L\leq 2\times10^9$。

问至少多少个 $8$ 连在一起组成的自然数是 $L$ 的倍数。

$x$ 个 $8$ 连在一起组成的正整数可写作 $\frac{8(10 ^x -1)}{9}$。题目要求我们求最小 $x$，使 $L|\frac{8(10 ^x -1)}{9}$。设 $d=\gcd(L,8)$。