期末速通

其他算法

快速幂

参考：洛谷P1226题解

让计算机求出 $a^b$，暴力相乘的话，电脑要计算 $b$ 次。用快速幂，计算次数在 $\mathrm{log}_{2} b$ 级别，很实用。

原理

  1. 如果将 $a$ 自乘一次，就会变成 $a^2$。再把 $a^2$ 自乘一次就会变成 $a^4$，然后是 $a^8$……自乘 $n$ 次的结果是 $a^{2^n}$。
  2. $a^x \cdot a^y = a^{x+y}$。
  3. 将 $b$ 转化为二进制看一下：比如 $b=(11)_{10}=(1011)_2$，从左到右，这些 1 分别代表十进制的 8,2,1。可以说 $a^{11}=a^8 \cdot a^2 \cdot a^1$。

为什么要这样表示？

因为在快速幂的过程中，我们会把 $a$ 自乘为 $a^2$，然后 $a^2$ 自乘为 $a^4$，以此类推，像上面第一条说的。

示例：已知 $a$，并且 $b=11$。求 $a^b$。

  1. 以电脑视角稍稍观察一下 $b=11$，二进制下是 $b=1011$。
  2. 制作一个base。现在 base = a，表示的是 $a^1=a$，base 会变。制作一个ans = 1，准备用来做答案。
  3. 开始循环
操作
循环一 看 $b$（二进制）的最后一位是1吗？是的。这代表 $a^{11}=a^8 \cdot a^2 \cdot a^1$ 中的 $\cdot a^1$ 存在。所以ans ∗= base。 因为1（二进制）的前面几位全部都是0，所以只有 $b$ 二进制最后一位是1时，b & 1才会返回 1。挺巧妙的，并且很快。 然后base努力上升，它通过自乘一次，使自己变成 $a^2$ 。同时 $b$ 把（二进制的）自己每一位都往右移动了。原来的最后第二位，变成了最后第一位！$b=(101)_2$。
循环二 再看看b，最后一位还是1。这说明有 $ \cdot a^2$，ans ∗= base。base继续努力，通过 base ∗= base让自己变成了 $a^4$。然后 $b$ 也右移一位。$b=10$
循环三 可是 $b$ 的最后一位不再是1了，说明不存在 $\cdot a^4$。base自我升华，达到了 $a^8$。且 b>>=1。这一步中，答案没有增加，可是毕竟 $b>0$，还有希望。
循环四 $b$ 的最后一位是1，这说明 $\cdot a^8$ 存在。ans ∗= base。由于b再右移一位就是0了，循环结束。

总的来说，如果 $b$ 在二进制上的某一位是 $1$，我们就把答案乘上对应的 $a^{2^n}$。

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

//求a的b次方
int quickPower(int a, int b) {
    int ans = 1, base = a;  // ans为答案，base为a^(2^n)
    while(b > 0) {
        if(b & 1) {         
            // b&1表示b在二进制下最后一位是不是1，
            // 如果是把ans乘上对应的a^(2^n)
            ans *= base;    
        }
        // base自乘，由a^(2^n)变成a^(2^(n+1))
        base *= base;  
        // 位运算，b右移一位，10010变成1001。
        // 现在b在二进制下最后一位是刚刚的倒数第二位。  
        b >>= 1;            
    }
    return ans;
}

二分答案

参考：博客园-量子流浪猫

二分答案是一种高效（偷懒）的算法技巧，通常用于解决最优化问题，尤其是当问题具有单调性时。它的核心思想是通过二分查找来快速缩小答案的范围，从而找到最优解。

实际上就是不断尝试，只不过使用二分法，时间复杂度低一点。

适用场景

  1. 最大值最小化或最小值最大化问题。
  2. 问题具有单调性，即当答案增大或减小时，问题的可行性会呈现单调变化。
  3. 直接求解问题较为复杂，但可以通过给定答案快速验证其可行性。

步骤

步骤 操作
确定搜索范围 根据问题的性质，确定答案的可能范围[left, right]。
计算中间值 mid = left + (right - left) / 2。
验证可行性 检查mid是否满足条件。
如果满足条件，缩小右边界right = mid，尝试寻找更优的解。
如果不满足条件，调整左边界left = mid + 1。
若left和right的差大于允许的误差值，返回到第二步。
终止条件 当left和right相遇（或两者之差小于允许的误差值）时，输出最优解。

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int binarySearchAnswer(int left, int right) {
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (check(mid)) { // 检查 mid 是否满足条件
            right = mid;  // 满足条件，尝试更小的值
        } else {
            left = mid + 1; // 不满足条件，尝试更大的值
        }
    }
    return left; // 返回最优解
}
 
bool check(int mid) {
    // 根据问题实现具体的检查逻辑
    // 返回 true 或 false
}

前缀和与差分

前缀和与差分是算法中常用的技巧，主要用于快速处理与区间操作相关的问题。

参考：博客园-Xbhog

前缀和

前缀和：数组该位置之前的元素之和。作用是快速求出元素组中某段区间的和。

前缀和类似于求一个数列 $a_n$ 的前 $n$ 项和 $S_n$。

进行前缀和运算时，下标从1开始。

1
2
3
4
5
6
7

// 设数组a[0] = 0
// 预处理：时间复杂度O(n)
prefix[1] = a[1]
prefix[2] = a[1]+a[2] = prefix[1]+a[2]
prefix[3] = a[1]+a[2]+a[3] = prefix[2] + a[3]
...
prefix[n] = a[1]+a[2]+...+a[n] = prefix[n-1]+a[n-1]

为什么下标要从1开始：方便后面的计算，避免下标转换，a[0] 设为零，不影响结果。

求数组中 $[l,r]$ 区间的和，如果使用普通循环，需要执行 $l-r$ 次：

1
2
3
4

int sum = 0;
for (int i = l; i <= r; i++) {
    sum += a[i];
}

而且如果需要求多个不同区间的和，重复计算将很频繁。

使用前缀和，只需要花费 $\mathrm{O}(n)$ 的时间构造前缀和数组，再求区间和时复杂度就降为 $\mathrm{O} (1)$。

定义两个数组，一个为原始数组a[]，一个为前缀和数组prefix[]：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <bits/stdc++.h>
using namespace std;

// 初始化原数组
int a[100], prefix[100];

int main() {
    int l,r,n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]
    }
    
    // 前缀和计算：prefix[i] = prefix[i-1]+a[i]
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i-1] + a[i];
    }
    
    // 输入区间范围[l,r]，prefix[r]-prefix[l-1]的结果就是所求区间的和
    cin >> l >> r;
    cout << prefix[r] - prefix[l-1];
    
    return 0;
}

差分

差分是前缀和的逆运算。作用：

  • 快速对一个数组的某个区间内所有元素进行相同的增量或减量操作。
  • 在需要对数组的多个区间进行批量操作时，差分方法可以显著降低复杂度。

重点：构造差分数组diff[]：

1
2
3
4
5

diff[1] = a[1]
diff[2] = a[2]-a[1]
diff[3] = a[3]-a[2]
...
diff[n] = a[n]-a[n-1]

diff[]称为a[]的差分。相应地，a[]称为diff[]的前缀和。对差分数组做加减操作，再通过计算差分数组的前缀和，会影响原数组相应范围内的所有元素。

 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

#include <bits/stdc++.h>
using namespace std;

int a[100], diff[100];

int main() {
    int l,r,n;
    cin >> n;
    for (int i = 1; i <= n ; i++) {
        cin >> a[i];
    }
    
    // 构造差分数组
    for (int i = 1; i <= n ; i++) {
        diff[i] = a[i]-a[i-1];
    }
    
    cin >> l >> r;      // 定义要更改的区间
    diff[l] += c;      // 实现区间[l,n]的所有元素+c
    diff[r+1] -= c;     // 实现区间[r+1,n]的所有元素-c
    
    // 将差分数组转换成原数组，也就是求差分数组的前缀和。
    for (int i = 1; i <= n ; i++) {
        // 类比prefix[i]=prefix[i-1]+a[i]
        a[i] = a[i-1]+diff[i];
    }
    
    return 0;
}

因为a[]数组是diff[]数组的前缀和，diff[]是a[]的差分，所以在diff[]的某个区间上+c会影响的a区间上的结果

KMP算法

参考：博客园 Higurashi-kagome

KMP算法是一个经典的字符串匹配算法，解决了朴素字符串匹配算法中因回溯次数过多而造成的时间复杂度过高的问题。

基本思路

在匹配字符串时，当发现某一个字符不匹配的时候，由于已经知道之前遍历过的字符，尽可能多地利用这些信息来避免指针回退的步骤。

这样主串的指针就会永远向前方移动，算法就可以改进为线性时间复杂度了。

步骤

当匹配失败时，模式串指针j要移动的下一个位置k应满足以下性质：模式串最前面的k-1个字符和j之前的最后k-1个字符一样。

我们把匹配失败时模式串指针j要移动的下一个位置k存储到next[]数组中。

这样，当匹配失败时，程序直接读取next[]数组中的值并赋值给指针j，重复匹配操作。

这样可以得出next[]数组的定义：

$$next[j] = \left\{\begin{matrix} 0 & j=1 \\\\ \mathrm{max}\{k | 1 < k < j 且 p_1 \cdots p_{k-1} == p_{j-k+1} \cdots p_{j-1}\} & 此集合非空 \\\\ 1 & 其他 \end{matrix}\right.$$

KMP算法的next[]数组有多种定义方式，这里采用的是严蔚敏《数据结构（C语言版）》的方法。

KMP算法

代码 

 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

// KMP算法主体
int KMP(string S, string T, int pos) {
    i = pos; j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[i]) {
            // 匹配成功时，继续比较后续字符
            i++; j++;
        }
        else {
            // 匹配失败时，模式串向右移动
            j = next[j];
        }
    }
    if (j > T[0]) {
        // 匹配成功
        return i-T[0];
    }
    return 0;
}

// 求next数组
void get_next(String T, int next[]) {
    i = 1; next[1] = 0; j = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            i++; j++; next[i] = j;
        }
        else {
            j = next[j];
        }
    }
}

扫描线算法

设有 $n$ 个活动的集合 $E=\{1,2, \cdots,n\}$，每个活动都要求互斥地使用同一资源。每个活动 $i$ 都有一个要求使用该资源的起始时间 $s_i$ 和一个结束时间 $f_i$，且 $s_i <f_i$（即如果选择了活动 $i$，则它在半开时间区间 $[s_i, f_i)$ 内占用资源）。

现所有活动都必须安排，求出最少需要几个资源。

算法思想

想象有一根"扫描线"从时间轴的最左边扫到最右边：

  • 每当扫描线遇到一个活动开始，就相当于“又有一个活动要用教室”，当前占用数 +1；
  • 每当扫描线遇到一个活动结束，就相当于“这个活动用完教室了”，当前占用数 -1。

在扫描过程中，当前占用数的最大值就是最少需要的教室数量。因为那一刻有那么多活动同时进行，你不可能把它们塞进比这更少的教室。

算法步骤

  1. 把每个活动的开始时间和结束时间各自拆成一个“事件”；
  2. 开始事件记为 +1（多一个活动在进行），结束事件记为 -1（少一个活动在进行）；
  3. 把所有事件按时间从小到大排序；
  4. 从头扫到尾，维护一个计数器cnt，遇到 +1 就加，遇到 -1 就减；
  5. 扫描过程中 cnt 的最大值就是最少教室数。
📝 备注

如果同一时刻既有开始又有结束，结束事件排在开始事件前面（即先 -1 后 +1）。

例如，像 $[1,2)$ 在 2:00 结束、$[2,4)$ 在 2:00 开始，这两个活动不重叠：2:00 教室腾出来了，下一场刚好接着用。如果结束不优先，会把不重叠的也误判成重叠。

例如，对于活动 $[1, 2)$，$[2, 4)$，$[6, 7)$，$[4, 8)$，则可以拆分为8个事件：

1
2
3
4

活动 A = [1, 2)  →  开始:1 (+1),  结束:2 (-1)
活动 B = [2, 4)  →  开始:2 (+1),  结束:4 (-1)
活动 C = [6, 7)  →  开始:6 (+1),  结束:7 (-1)
活动 D = [4, 8)  →  开始:4 (+1),  结束:8 (-1)

把所有事件按时间排序（同一时刻，结束 -1 排在开始 +1 前面），从前到后扫描一遍并维护计数器cnt，它的最大值即为所求的结果。

1
2
3
4
5
6
7
8

时刻 1: +1 (A 开始)      → cnt = 1       ← 最大值目前 = 1
时刻 2: -1 (A 结束)      → cnt = 0
时刻 2: +1 (B 开始)      → cnt = 1
时刻 4: -1 (B 结束)      → cnt = 0
时刻 4: +1 (D 开始)      → cnt = 1
时刻 6: +1 (C 开始)      → cnt = 2       ← 最大值更新为 2！
时刻 7: -1 (C 结束)      → cnt = 1
时刻 8: -1 (D 结束)      → cnt = 0

扫描线算法

这个算法模型可以轻松适配很多类似场景：

  • 最多同时在线人数：给定用户的登录登出时间，求峰值在线人数。
  • 最少站台数：给定火车的到站和离站时间，求车站最少需要多少站台。
  • 重叠最大数：在数轴上，求被最多区间覆盖的点的覆盖次数（差分数组思想）。
  • 资源调度：如果有 $K$ 个资源，只需判断扫描过程中的 current 是否曾超过 $K$。
© 2025 - 2026 RunicDolphin806
网站总访客数：Loading

使用 Hugo 构建
主题 Stack 由 Jimmy 设计