介绍倍增算法+三道例题，题目来自洛谷，难度至少提高+/省选-。

        倍增算法在之前的快速幂、求LCA算法、ST表中都有体现，它基于下面的基本原理：

        也就是说，对于任意一个自然数，它都可以唯一地表示成若干个互异的2的方幂相加的形式。利用这个原理，我们可以将x的求得过程降至对数级别。
        在实际操作中，通常采用“跳跃式行进”的方法去应用倍增，具体做法是：从2的高幂次方幂开始进行跳跃，如果越过目标，则将方幂减少一倍（即下一个方幂）；如果未越过，可以证明该方幂一定在上面给出的二进制拆分表达式中，进行跳跃操作，之后也需要将方幂减少一倍。重复这个过程直到取尽2的所有自然数方幂，此时就已经跳跃到目标位置。这样可以在$O(logn)$复杂度下完成跳跃操作。
        下面三道例题，点击题目标题可进行跳转。样例及说明略，见洛谷原题。

例题一　货车运输(P1967)

难度：提高+/省选-

题目描述

        A国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：

        第一行有两个用一个空格隔开的整数 n,m，表示A国有n座城市和 m 条道路。
        接下来m行每行 3 个整数 x, y, z，每两个整数之间用一个空格隔开，表示从 x 号城市到y号城市有一条限重为z的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。
        接下来一行有一个整数 q，表示有 q 辆货车需要运货。
        接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

输出格式：

        共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。

题解

        这题本质上是求图中任意两点可能路径中最小边权值的最大值。看到最小值的最大值首先想到二分答案，二分答案比暴力快，但是免不了每次都要遍历一遍图，效率低下一定TLE。
        考虑其它方法。可以证明任意两点最大值出现的路径一定在该图的最大生成树上，于是用Kruskal算法配合并查集求出最大生成树。
        树构造完毕后，两点的路径显然就是经过两个点LCA的路径，这里改一下倍增法求LCA的步骤就可以轻易求出答案。查询时间复杂度$O(logn)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>

#define N 10005
#define inf 0x7ffffff
using namespace std;

inline int read() {//神奇的读入优化
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

struct Edge {
    int to, v, next;
} edge[N];

struct Temp {
    int from, to, v;

    bool operator<(Temp t) {
        return v > t.v;
    }
} temp[5 * N];

int n, m, head[N], cnt = 1, father[N], grand[N][16], minn[N][16], depth[N];

inline void add(int x, int y, int z) {
    edge[cnt].v = z, edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

int find(int x) {
    return father[x] == x ? x : father[x] = find(father[x]);
}

void DFS(int x) {
    for (int i = head[x]; i; i = edge[i].next)
        if (!depth[edge[i].to]) {
            grand[edge[i].to][0] = x, minn[edge[i].to][0] = edge[i].v, depth[edge[i].to] = depth[x] + 1;
            for (int j = 1; j <= 15; j++) {
                grand[edge[i].to][j] = grand[grand[edge[i].to][j - 1]][j - 1];
                minn[edge[i].to][j] = min(minn[edge[i].to][j - 1], minn[grand[edge[i].to][j - 1]][j - 1]);
            }
            DFS(edge[i].to);
        }
}

int findAns(int x, int y) {
    if (x == y)return inf;
    if (find(x) != find(y))return -1;
    int ans = inf;
    if (depth[x] == depth[y]) {
        for (int i = 15; i >= 0; i--) {
            if (grand[x][i] != grand[y][i])
                ans = min(ans, min(minn[x][i], minn[y][i])), x = grand[x][i], y = grand[y][i];
        }
        return min(ans, min(minn[x][0], minn[y][0]));
    } else {
        if (depth[x] < depth[y]) {
            for (int i = 15; i >= 0; i--) {
                if (depth[grand[y][i]] >= depth[x])ans = min(ans, minn[y][i]), y = grand[y][i];
            }
            return min(ans, findAns(x, y));
        } else {
            for (int i = 15; i >= 0; i--) {
                if (depth[grand[x][i]] >= depth[y])ans = min(ans, minn[x][i]), x = grand[x][i];
            }
            return min(ans, findAns(x, y));
        }
    }
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        father[i] = i;
        for (int j = 0; j <= 15; j++)minn[i][j] = inf;
    }
    for (int i = 1; i <= m; i++)temp[i].from = read(), temp[i].to = read(), temp[i].v = read();
    sort(temp + 1, temp + m + 1);
    for (int i = 1; i <= m; i++)
        if (find(temp[i].from) != find(temp[i].to)) {
            father[find(temp[i].from)] = find(temp[i].to);
            add(temp[i].from, temp[i].to, temp[i].v);
            add(temp[i].to, temp[i].from, temp[i].v);
        }
    for (int i = 1; i <= n; i++)if (!depth[i])depth[i] = 1, DFS(i);
    int q = read();
    for (int i = 1; i <= q; i++) {
        int x = read(), y = read();
        cout << findAns(x, y) << endl;
    }
    return 0;
}

例题二　开车旅行(P1081)

难度：省选/NACM-

题目描述

        小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i的海拔高度为$H_i$ ，城市i和城市j之间的距离$d_{ij}$恰好是这两个城市海拔高度之差的绝对值，即$d_{ij}=|H_i-H_j|$。
        旅行过程中，小 A和小B 轮流开车，第一天小 A 开车，之后每天轮换一次。他们计划选择一个城市 S 作为起点，一直向东行驶，并且最多行驶 X公里就结束旅行。小 A 和小 B的驾驶风格不同，小 B总是沿着前进方向选择一个最近的城市作为目的地，而小 A总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 X 公里，他们就会结束旅行。
        在启程之前，小 A想知道两个问题：
        对于一个给定的 $X=X_0$，从哪一个城市出发，小 A开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
        对任意给定的 $X=X_i$和出发城市 $S_i$，小 A开车行驶的路程总数以及小 B 行驶的路程总数。

输入输出格式

输入格式：

        第一行包含一个整数N，表示城市的数目。
        第二行有 N个整数，每两个整数之间用一个空格隔开，依次表示城市 1 到城市 N的海拔高度，即$H_1,H_2,\cdots,H_n$，且每个$H_i$都是不同的。
        第三行包含一个整数$X_0$。
        第四行为一个整数M，表示给定M组$S_i$和$X_i$。
        接下来的 M 行，每行包含 2 个整数$S_i$和$X_i$，表示从城市$S_i$出发，最多行驶$X_i$公里。

输出格式：

        输出共 M+1行。
        第一行包含一个整数$S_0$ ，表示对于给定的$X_0$，从编号为$S_0$的城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值最小。
        接下来的M行，每行包含 2个整数，之间用一个空格隔开，依次表示在给定的$S_i$和$X_i$下小 A 行驶的里程总数和小 B 行驶的里程总数。

题解

        本题有一定难度。首先应该考虑预处理出每一个城市小A的目标和小B的目标。最直接的方法是暴力扫一遍找出最小和第二小，时间复杂度$O(n^2)$。在这样的数据量下，仅这个步骤就已经TLE了，显然不可取。
        一个较好的方法是从右向左进行预处理，每一次保证待求城市右侧的城市的高度升序（降序也可），然后二分求最小和次小。这样需要向有序序列中不断插入元素，还要保证能够二分，可以选择用平衡树这个数据结构完成这个操作，这里用fhq treap。平衡树操作求第二小可以先求最小再将其最小值删除，再求的最小值就是实际的第二小，紧接着把最小值重新插入即可。预处理时间复杂度$O(nlogn)$。
        然后考虑后面的操作。对于小A的第一个问题，一种想法是遍历出发城市进行判断，这样做的时间复杂度仍然为$O(n^2)$，会TLE，于是采用倍增算法将其优化至$O(nlogn)$。预处理出从某个城市开始走$2^k$步的目标城市和小A、小B的驾驶距离，进行倍增即可。第二个问题也可以用倍增的方法解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>

#define N 100005
#define ABS(x) ((x)>=0?(x):-(x))
using namespace std;
struct Node {
    int v, ch[2], key, rk;
} node[N << 1];
int cnt = 1, root, to[N][2], op[N], n;
int A[N][2][19], B[N][2][19], TO[N][2][19];

inline int read() {
    char e = getchar();
    int s = 0, f = 0;
    while (e < '-')e = getchar();
    if (e == '-')f = 1, e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return f ? -s : s;
}

void split(int rt, int &a, int &b, int k) {
    if (rt == 0)a = b = 0;
    else {
        if (node[rt].v <= k)a = rt, split(node[rt].ch[1], node[a].ch[1], b, k);
        else b = rt, split(node[rt].ch[0], a, node[b].ch[0], k);
    }
}

void merge(int &rt, int a, int b) {
    if (a == 0 || b == 0)rt = a + b;
    else if (node[a].key < node[b].key)rt = b, merge(node[rt].ch[0], a, node[b].ch[0]);
    else rt = a, merge(node[rt].ch[1], node[a].ch[1], b);
}

int newNode(int x, int rk) {
    node[cnt].v = x, node[cnt].key = rand(), node[cnt].rk = rk;
    return cnt++;
}

void insert(int x, int rk) {
    int p = newNode(x, rk), a, b;
    split(root, a, b, x), merge(a, a, p), merge(root, a, b);
}

void del(int x) {
    int a, b, c;
    split(root, a, b, x), split(a, a, c, x - 1), merge(root, a, b);
}

int findMin(int rt, int x) {
    if (rt == 0)return 0;
    int ans;
    if (node[rt].v < x)ans = findMin(node[rt].ch[1], x);
    else ans = findMin(node[rt].ch[0], x);
    if (ans == 0)return rt;
    if (ABS(node[ans].v - x) < ABS(node[rt].v - x))return ans;
    else if (ABS(node[ans].v - x) > ABS(node[rt].v - x))return rt;
    else return node[ans].v < node[rt].v ? ans : rt;
}

int findMin2(int x, int a) {
    del(node[a].v);
    int ans = findMin(root, x);
    insert(node[a].v, node[a].rk);
    return ans;
}

inline void solve() {
    int x0 = read(), ans = 1, m;
    double minn = 1e9, tp;
    for (int i = 1; i <= n; i++) {
        int p = i, a = 0, b = 0;
        for (int j = 18; j >= 0; j--)
            if (TO[p][0][j] != 0 && a + b + A[p][0][j] + B[p][0][j] <= x0)
                a += A[p][0][j], b += B[p][0][j], p = TO[p][0][j];
        tp = (b == 0 ? 1e9 : (double) a / b);
        if (tp < minn)ans = i, minn = tp;
        else if (tp == minn && op[i] > op[ans])ans = i;
    }
    cout << ans << endl;
    m = read();
    for (int i = 1; i <= m; i++) {
        int S = read(), X = read(), a = 0, b = 0;
        for (int j = 18; j >= 0; j--) {
            if (TO[S][0][j] != 0 && a + b + A[S][0][j] + B[S][0][j] <= X) {
                a += A[S][0][j], b += B[S][0][j], S = TO[S][0][j];
            }
        }
        cout << a << " " << b << endl;
    }
}

int main() {
    srand(time(NULL));
    n = read();
    for (int i = 1; i <= n; i++)op[i] = read();
    insert(op[n], n);
    for (int i = n - 1; i >= 1; i--)
        to[i][1] = findMin(root, op[i]), to[i][0] = findMin2(op[i], to[i][1]), insert(op[i], i);
    for (int i = 1; i <= n; i++)to[i][0] = node[to[i][0]].rk, to[i][1] = node[to[i][1]].rk;
    for (int i = n - 1; i >= 1; i--) {
        A[i][0][0] = ABS(op[i] - op[to[i][0]]), B[i][1][0] = ABS(op[i] - op[to[i][1]]);
        TO[i][0][0] = to[i][0], TO[i][1][0] = to[i][1];
        for (int j = 1; j <= 18; j++) {
            TO[i][0][j] = TO[TO[i][0][j - 1]][j == 1][j - 1];
            TO[i][1][j] = TO[TO[i][0][j - 1]][j != 1][j - 1];
            A[i][0][j] = A[i][0][j - 1] + (j == 1 ? 0 : A[TO[i][0][j - 1]][0][j - 1]);
            B[i][1][j] = B[i][1][j - 1] + (j == 1 ? 0 : B[TO[i][1][j - 1]][1][j - 1]);
            A[i][1][j] = A[i][1][j - 1] + (j == 1 ? A[TO[i][1][0]][0][0] : A[TO[i][1][j - 1]][1][j - 1]);
            B[i][0][j] = B[i][0][j - 1] + (j == 1 ? B[TO[i][0][0]][1][0] : B[TO[i][0][j - 1]][0][j - 1]);
        }
    }
    solve();
    return 0;
}

例题三　跑路(P1613)

难度：提高+/省选-

题目描述

        小A的工作不仅繁琐，更有苛刻的规定，要求小A每天早上在6：00之前到达公司，否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资，小A买了一个十分牛B的空间跑路器，每秒钟可以跑2^k千米（k是任意自然数）。当然，这个机器是用longint存的，所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图，小A家为点1，公司为点n，每条边长度均为一千米。小A想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证1到n至少有一条路径。

输入输出格式

输入格式：

        第一行两个整数n，m，表示点的个数和边的个数。
        接下来m行每行两个数字u，v，表示一条u到v的边。

输出格式：

        一行一个数字，表示到公司的最少秒数。

题解

        其实是一道水题，能想出来方法则这题很简单，想不出来…就想不出来了。
        预处理任意两点间是否存在长度为$2^k$的路径，可以使用邻接矩阵快速幂。对于存在该路径的点对，显然可以用1s的时间在两点间“穿越”，相当于两点间有一条权为1的有向边。以此加边构图，最后结点1到结点n的最短路径就是答案，这里可以用Floyd算法求出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>

using namespace std;
int n, m;
long long dict[51][51];

struct Matrix {
    int op[51][51];

    void operator*=(Matrix p) {
        int t[51][51] = {0};
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                for (int z = 1; z <= n; z++)t[i][j] += this->op[i][z] * p.op[z][j];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)this->op[i][j] = t[i][j] >= 1;
    }
}a;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)dict[i][j] = i == j ? 0 : (1l << 52);
    }
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        a.op[x][y] = 1, dict[x][y] = 1;
    }
    for (int i = 2; i <= 63; i++) {
        a *= a;
        for (int j = 1; j <= n; j++) {
            for (int z = 1; z <= n; z++)if (a.op[j][z])dict[j][z] = 1;
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (k != i && i != j && k != j) {
                    dict[i][j] = min(dict[i][k] + dict[k][j], dict[i][j]);
                }
            }
        }
    }
    cout << dict[1][n];
    return 0;
}