OI学习笔记 - 算法竞赛实用小工具

发表于 更新于 阅读次数： 本文字数： 9.4k 阅读时长 ≈ 17 分钟

信息学竞赛实用内置算法与技巧学习笔记

算法复杂度概述

在信息学竞赛中, 算法的时间复杂度和空间复杂度是衡量算法效率的重要指标.为了更全面地分析算法性能, 我们还需要了解均摊复杂度的概念及其计算方式.

时间复杂度计算方式

时间复杂度主要通过分析算法中基本操作的执行次数来确定.基本操作通常是循环、比较、算术运算等.

  • 排序算法(sort): 排序算法的时间复杂度通常由比较和交换操作的次数决定.快速排序的平均时间复杂度为 O(n log n), 其中 n 是待排序元素的数量.这是因为快速排序将数组分成两部分, 递归排序每一部分, 并且每次递归处理大约需要 O(n) 的时间.递归深度为 O(log n), 因此总时间复杂度为 O(n log n).
  • 二分查找算法(binary_search): 二分查找的时间复杂度为 O(log n), 其中 n 是有序数组的大小.这是因为每次比较将搜索范围减半, 直到找到目标元素或搜索范围为空.比较的次数与数组大小的对数成正比.
  • 生成下一个排列(next_permutation): next_permutation 的时间复杂度为 O(n), 其中 n 是排列的长度.这是因为算法需要遍历整个排列来找到合适的元素进行交换和反转操作.
  • PBDS(ordered_set)操作: ordered_set 的插入、删除和查找操作的时间复杂度均为 O(log n), 其中 n 是集合中元素的数量.这是因为 ordered_set 基于红黑树实现, 红黑树的高度保持在 O(log n), 因此这些操作的时间复杂度由树的高度决定.

空间复杂度计算方式

空间复杂度主要通过分析算法所需额外存储空间的大小来确定.

  • 排序算法(sort): 通常为原地排序, 空间复杂度为 O(1)(不考虑递归栈空间).但对于某些实现(如递归快速排序), 在最坏情况下空间复杂度可能为 O(n).
  • 二分查找算法(binary_search): 空间复杂度为 O(1), 只需要少量的额外变量来存储中间结果.
  • 生成下一个排列(next_permutation): 空间复杂度为 O(1), 除了输入的排列数组外, 不需要额外的存储空间.
  • PBDS(ordered_set): 每个元素需要额外的指针来维护树的结构, 空间复杂度为 O(n), 其中 n 是集合中元素的数量.

均摊复杂度介绍及计算方式

均摊复杂度用于分析一系列操作的平均时间复杂度, 特别是在某些操作可能偶尔具有较高的时间复杂度, 但其他操作具有较低的时间复杂度的情况下.均摊复杂度通过将较高成本的操作分摊到其他低操作成本的操作上, 从而得到一个平均的时间复杂度.

示例: 动态数组(vector)的扩容操作

当向动态数组(如 C++ 的 vector)中添加元素时, 如果数组已满, 需要进行扩容操作, 这通常涉及创建一个更大的数组并将现有元素复制到新数组中.扩容操作的时间复杂度为 O(n), 其中 n 是当前数组的大小.然而, 扩容操作并不频繁发生, 只有在数组满时才会进行.在连续的 m 次添加操作中, 扩容操作只发生几次(例如, 当数组初始大小为 1, 每次扩容为原来的两倍时, 扩容次数为 log2(m) 次).

总的元素复制次数为:

1 + 2 + 4 + ... + n/2 = n - 1

因此, 对于 m 次添加操作, 总的时间复杂度为 O(m + n) = O(m), 因为 n ≤ m.因此, 每次添加操作的均摊时间复杂度为 O(1).

代码示例: 动态数组的扩容及均摊复杂度分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec;
    int n;
    cin >> n; // 输入要添加的元素数量
    for (int i = 0; i < n; ++i) {
        vec.push_back(i); // 添加元素, 自动扩容
    }
    // 输出所有元素
    for (int x : vec) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

算法复杂度总结

算法 时间复杂度 空间复杂度 均摊复杂度(适用情况)
排序算法(sort) O(n log n) O(1) 或 O(n) 不适用
二分查找算法(binary_search) O(log n) O(1) 不适用
生成下一个排列(next_permutation) O(n) O(1) 不适用
PBDS(ordered_set)操作 O(log n) O(n) 不适用
动态数组(vector)扩容 O(n)(单次扩容) O(n) O(1)(均摊, 每次添加操作)

常用内置算法

sort(排序算法)

使用方式

在信息学竞赛中, sort 是最常用的排序算法, 其底层实现为 快速排序和堆排序.基本语法为 std::sort(first, last, compare), 其中 first 和 last 分别是待排序区间的起始和结束迭代器, compare 是可选的比较函数.

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {5, 2, 9, 1, 5, 6};
    sort(arr.begin(), arr.end()); // 升序排序
    // sort(arr.begin(), arr.end(), greater<int>()); // 降序排序
    for (int x : arr) cout << x << " ";
    return 0;
}

优化点

  • 对于大数据量的排序, 可以考虑使用快排的优化版本, 或者使用其他排序算法(如归并排序)手动实现, 但一般情况下 sort 已足够高效.
  • 当需要自定义排序规则时, 可以使用函数对象或 λ 表达式(C++11 及以上).

自定义排序示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val, id;
};

bool cmp(Node a, Node b) {
    if (a.val != b.val) return a.val < b.val;
    return a.id < b.id;
}

int main() {
    vector<Node> nodes = {{5, 1}, {2, 2}, {9, 3}, {1, 4}, {5, 5}, {6, 6}};
    sort(nodes.begin(), nodes.end(), cmp);
    for (auto node : nodes) cout << node.val << " " << node.id << endl;
    return 0;
}

相关例题及解决方式

  • 波比喝水(P1095).
  • 题目要求我们计算波比在喝水过程中, 每次喝水的水量和时间的关系.首先, 我们需要将所有的喝水事件按照时间顺序排序, 这样才能正确地计算每一段时间内的水量变化.排序是解决这个问题的第一步, 也是关键的一步.使用 sort 函数可以方便地对时间进行排序.
  • 我们需要定义一个结构体来存储每个喝水事件的时间和水量, 然后按照时间从小到大排序, 最后按顺序计算总水量即可.

解决代码:

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
#include <bits/stdc++.h>
using namespace std;

struct Event {
    int time, water;
};

bool cmp(Event a, Event b) {
    return a.time < b.time;
}

int main() {
    int n;
    cin >> n;
    vector<Event> events(n);
    for (int i = 0; i < n; ++i) {
        cin >> events[i].time >> events[i].water;
    }
    sort(events.begin(), events.end(), cmp);
    int total = 0;
    for (int i = 0; i < n; ++i) {
        total += events[i].water;
        cout << total << endl;
    }
    return 0;
}

二分查找算法

使用方式

用于判断某个元素是否存在于已排序的区间内.

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int target = 5;
    bool found = binary_search(arr.begin(), arr.end(), target);
    cout << (found ? "存在" : "不存在") << endl;
    return 0;
}

优化点

  • 在实际使用中, 通常会结合 lower_bound 或 upper_bound 来获取元素的位置, 而不是仅仅判断是否存在.
  • 可以使用自定义比较函数来适应不同的数据类型和查找规则.

示例代码(结合 lower_bound)

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int target = 5;
    auto it = lower_bound(arr.begin(), arr.end(), target);
    if (it != arr.end()) {
        cout << "First element >= " << target << " is at position " << (it - arr.begin()) << endl;
    }
    return 0;
}

相关例题及解决方式

  • 题目: 数的范围(P1315).
  • 思考过程: 题目要求我们找出一个数字在有序数组中的左右边界.我们可以通过二分查找来确定数字的最小和最大位置.首先, 我们需要一个函数来找到第一个大于或等于目标值的元素位置, 然后另一个函数来找到第一个大于目标值的元素位置, 这两个位置之间的元素就是我们要找的数字的所有出现位置. binary_search 相关的函数可以帮助我们高效地实现这一目标.
  • 解决方式: 使用 binary_search 确定目标值存在后, 分别使用 lower_bound 和 upper_bound 找到目标值的第一个和最后一个位置.

解决代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    if (!binary_search(arr.begin(), arr.end(), target)) {
        cout << "Not Found" << endl;
        return 0;
    }
    auto left = lower_bound(arr.begin(), arr.end(), target);
    auto right = upper_bound(arr.begin(), arr.end(), target);
    cout << left - arr.begin() << " " << right - arr.begin() - 1 << endl;
    return 0;
}

next_permutation(生成下一个排列)

使用方式

用于生成当前排列的下一个字典序排列.

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {1, 2, 3};
    do {
        for (int x : arr) cout << x << " ";
        cout << endl;
    } while (next_permutation(arr.begin(), arr.end()));
    return 0;
}

优化点

  • 在处理全排列问题时, 可以先对数组进行排序, 然后使用 next_permutation 依次生成所有排列, 避免自己实现排列生成算法可能出现的错误.
  • 对于大数据量的排列生成, 需要注意时间复杂度, 因为每次调用 next_permutation 的时间复杂度为 O(n).

示例代码(全排列)

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "ABC";
    sort(s.begin(), s.end());
    do {
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

相关例题及解决方式

  • 题目: 全排列(P1051).
  • 思考过程: 题目要求输出一个字符串的所有排列.最直接的方法是生成所有可能的排列并输出. next_permutation 函数可以方便地帮助我们生成下一个排列, 我们只需要在一个循环中不断调用它, 直到所有排列都被生成.
  • 解决方式: 对字符串进行排序, 然后在一个循环中不断调用 next_permutation 生成所有排列并输出.

解决代码:

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    do {
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

四、命名空间

在信息学竞赛中, 为了方便编写代码, 通常会使用 using namespace std; 这样可以省去在代码中频繁使用 std:: 前缀.

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {5, 2, 9, 1, 5, 6};
    sort(arr.begin(), arr.end());
    for (int x : arr) cout << x << " ";
    return 0;
}

但是, 在一些复杂项目中, 过多地使用 using namespace 可能会导致命名冲突, 但在竞赛环境下, 这种写法是被广泛接受的.

五、λ 表达式

使用方式

λ 表达式可以用于定义匿名函数, 常用于自定义排序规则等场景.

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {5, 2, 9, 1, 5, 6};
    sort(arr.begin(), arr.end(), [](int a, int b) { return a > b; }); // 降序排序
    for (int x : arr) cout << x << " ";
    return 0;
}

优化点

  • λ 表达式可以使代码更加简洁, 减少定义额外函数或函数对象的麻烦.
  • 可以捕获外部变量(通过值或引用), 以实现更灵活的自定义逻辑.

示例代码(捕获外部变量)

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;

int main() {
    int factor = 2;
    vector<int> arr = {5, 2, 9, 1, 5, 6};
    sort(arr.begin(), arr.end(), [factor](int a, int b) { return a * factor < b * factor; });
    for (int x : arr) cout << x << " ";
    return 0;
}

六、pb_ds(Policy-Based Data Structures)

使用方式

pb_ds 是 GNU C++ 提供的一组数据结构扩展库, 包含哈希表、树状数据结构等.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main() {
    ordered_set s;
    s.insert(5);
    s.insert(2);
    s.insert(9);
    s.insert(1);
    s.insert(5);
    s.insert(6);
    cout << *s.find_by_order(2) << endl; // 输出第 3 小的元素(索引从 0 开始)
    cout << s.order_of_key(5) << endl; // 输出小于 5 的元素个数
    return 0;
}

优化点

  • ordered_set 可以在 O(log n) 时间内完成插入、删除、查找等操作, 并且支持按序号查找和查找序号等功能, 对于一些需要频繁进行这些操作的题目非常有用.
  • pb_ds 还提供了其他高效的数据结构, 如 hash 表(可以解决 STL 中 map 在某些情况下的性能问题)等.

示例代码(哈希表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef gp_hash_table<int, int> HashMap;

int main() {
    HashMap mp;
    mp[1] = 10;
    mp[2] = 20;
    mp[3] = 30;
    cout << mp[2] << endl;
    return 0;
}

相关例题及解决方式

  • 题目: 前驱后继问题(P3377).
  • 思考过程: 题目要求我们找到一个数在集合中的前驱和后继.传统的数据结构如 vector 和 set 可以实现, 但效率较低. ordered_set 提供了高效的查找前驱和后继的功能, 可以在 O(log n) 时间内找到答案, 这使得我们可以快速地解决问题.
  • 解决方式: 使用 ordered_set 的成员函数 find_by_order 和 order_of_key 来找到前驱和后继.例如, 对于给定的数 x, 前驱是 find_by_order(order_of_key(x) - 1), 后继是 find_by_order(order_of_key(x)).

解决代码:

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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main() {
    ordered_set s;
    int m;
    cin >> m;
    while (m--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            s.insert(x);
        } else if (op == 2) {
            if (s.order_of_key(x) > 0) {
                cout << *s.find_by_order(s.order_of_key(x) - 1) << endl;
            } else {
                cout << "None" << endl;
            }
        } else if (op == 3) {
            auto it = s.find_by_order(s.order_of_key(x));
            if (it != s.end()) {
                cout << *it << endl;
            } else {
                cout << "None" << endl;
            }
        }
    }
    return 0;
}

以上就是信息学竞赛中一些实用的内置算法和技巧的学习笔记, 在实际竞赛中, 灵活运用这些工具可以大大提高解题效率, 但同时也需要深入理解其原理和适用场景, 才能更好地应对各种复杂的题目.