发表更新算法基础课1 小时读完 (大约11429个字)

第一章 基础算法

排序

快速排序

主要思想：分治

时间复杂度：O(n*log{2}{n})【平均时间复杂度，最快可以达到n^2】

e.g. 对数组q的序号l至r区域进行排序

  1. 确定分界点x（数值）：常用——左边界q[l]、**中心点处值q[(l+r)/2]**、右边界q[r]、随机
  2. 调整区间：使所有小于（等于）x的值均位于x左侧，所有大于（等于）x的值都位于x右侧（区间内不要求有序）
    • 暴力做法（时间复杂度仍为O(n)，但会额外耗费空间）：
      1. 新开两个数组a[]，b[]
      2. 对数组q的序号l至r区间进行扫描：
        • 若q[i]≤x，将q[i]放入a[]
        • 若q[i]≥x，将q[i]放入b[]
      3. 将a[]、b[]依次放回q[]中
    • 推荐做法（使用指针）：
      1. 从左边界q[l]处开始，使用指针i向右侧移动，若指针指向的数值大于等于x，停下
      2. 从右边界q[r]处开始，使用指针j向左侧移动，若指针指向的数值小于等于x，停下
      3. 交换指针i、j处的数值
      4. 重复1、2、3步骤（在移动后的指针i、j位置基础上继续向右/左侧移动），直到两个指针相遇
  3. 递归处理左右两段

例题：785. 快速排序 - AcWing题库

给定一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10^9范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

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
#include <iostream>

using namespace std;

const int N = 100010; // 保险，防止边界问题

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    //判定边界：区间内只有一个数或没有数时不需要排序
    if (l >= r)
        return;
    
    int x = q[(l + r) / 2], i = l - 1, j = r + 1; //取分界值
    //注意：由于每次完成交换（包括初始状态）都自动向中间移动一格，初始时要将两侧指针取在区间外侧1个单位
    while (i < j) //迭代：移动+交换
    {
        do
            i ++ ;
        while (q[i] < x);
        do
            j -- ;
        while (q[j] > x);
        if (i < j)
        {
            //交换两数:swap(q[i], q[j]);
            int t = q[i];
            q[i] = q[j];
            q[j] = t;
        }
    }
    
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &q[i]);
    
    quick_sort(q, 0, n-1);
    
    for (int i = 0; i < n; i ++ )
        printf("%d ", q[i]);
    
    return 0;
}

归并排序

主要思想：分治

时间复杂度：O(n*log{2}{n})

  • 时间复杂度计算：每次递归将当前序列分为2份（原序列->2份->4份->8份->……），直到每一份的长度为1时停止；显然这样的递归需要进行log{2}{n}轮，而对于每一轮而言又需要进行时间复杂度为O(n)的归并，因此整体排序算法的时间复杂度为两者相乘，即O(n*log{2}{n})

e.g. 对数组q的序号l至r区域进行排序

  1. 确定分界点：以数组中心点mid = (l+r)/2为分界点，将数组q分成Left、Right两部分
  2. 对两部分进行递归排序，使其各自成为有序序列
  3. 归并：将两个有序数组合并成一个有序数组
    • 双指针算法（时间复杂度为O(n)）：
      1. 对于两个有序数组Left、Right而言，分别在其左端点处放置一个指针
      2. 比较两个数组指针处数值的大小，将更小的那一个放入输出的目标数组（初始为空）
        • 注意：若两个数组指针处数值大小相等，则优先将数组Left中的数值放入输出目标数组，则可保证排序算法的稳定
        • 排序算法的稳定：排序完成后，原数组中值相同的数之间的相对位置不变（归并排序稳定，快速排序不稳定；若想使快速排序稳定，需要在对数值排序的基础上对各元素在原数组中的位置序号进行排序）
      3. 对于更小的数值所在的数组而言，将指针向后移一位，重复步骤2（依次排入输出目标数组中）
      4. 重复步骤3，直到某个数组中所有的数全部被放入输出目标数组，则跳出循环，将另一个数组的所有剩余数值依次排入输出目标数组中，归并完成

例题：787. 归并排序 - AcWing题库

给定一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10^9范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

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
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int q[N], tmp[N]; //tmp：辅助数组

void merge_sort(int q[], int l, int r)
{
    //判定边界：区间内只有一个数或没有数时不需要排序
    if (l >= r)
        return;
    
    int mid = (l + r) / 2; //取分界点：当前区间中点
    
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    
    // 归并过程
    int k = 0, i = l, j = mid + 1; //k：当前tmp中已有数值个数；i、j：指向左、右半边起点指针
    while (i <= mid && j <= r)
        if (q[i] <= q[j])
            tmp[k ++ ] = q[i ++ ];
    	else
            tmp[k ++ ] = q[j ++ ];
    while (i <= mid)
        tmp[k ++ ] = q[i ++ ];
    while (j <= r)
        tmp[k ++ ] = q[j ++ ];
    
    for (i = l, j = 0; i <= r; i ++, j ++ )
        q[i] = tmp[j];
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &q[i]);
    
    merge_sort(q, 0, n-1);
    
    for (int i = 0; i < n; i ++ )
        printf("%d ", q[i]);
    
    return 0;
}

调用库函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int q[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &q[i]);
    
    sort(q, q + n);
    
    for (int i = 0; i < n; i ++ )
        printf("%d ", q[i]);
    
    return 0;
}

实测三种排序方法的运行时间相近。

二分查找

整数二分

  • 数组有单调性一定可以进行二分查找，但二分查找并不一定要求数组有单调性
  • （整数）二分查找的本质【基本思想】：以区间中心点为分割点，每次都选择查找目标所在的半部分区间进行下一步操作（分割+选择区间）；过程中保证选定区间内必然有查找目标（不存在该目标的情况除外，注意：二分法查找必然会有返回结果，但不存在该目标的情况下会返回满足筛选性质的元素中与目标值最接近的数值，因此需要额外判定输出是否与目标值相等），当区间长度为1时，该元素即为查找目标
  • 二分法查找必然会有返回结果

研究对象：数组q的序号l至r区域

若对于数组中要查找的某点数值，其一侧所有数均满足某一性质，而另一侧所有数均不满足该性质，则可通过二分查找找出该点。假定要查找的该点数值也满足这一点性质，根据满足性质的区间位于该点左侧/右侧，可以有两种查找方式：

  • 满足性质的区间位于该点左侧

    1. 取数组中心点mid = (l+r**+1**)/2处数值q[(l+r+1)/2]，判断其是否满足选定性质：

      • 若该点处数值满足选定性质，说明要查找的值应位于数组q的**[mid**, r]区间内，此时更新查找区间[l, r]为**[mid, r]（即令l=mid）**
      • 若该点处数值不满足选定性质，说明要查找的值应位于数组q的[l, mid - 1]区间内，此时更新查找区间[l, r]为[l, mid - 1]（即令r=mid-1）

      取数组中心点时需要+1的原因：

      当查找区间长度为1时，由于除法会向下取整，导致此时的mid=l，这样再令l=mid就会进入死循环

    2. 在新的查找区间内重复步骤1以进一步缩小查找区间，直到查找区间长度为0（区间两端坐标相同），该坐标点的数即为查找目标

  • 满足性质的区间位于该点右侧

    1. 取数组中心点mid = (l+r)/2处数值q[(l+r)/2]，判断其是否满足选定性质：
      • 若该点处数值满足选定性质，说明要查找的值应位于数组q的[l, mid]区间内，此时更新查找区间[l, r]为[l, mid]（即令r=mid）
      • 若该点处数值不满足选定性质，说明要查找的值应位于数组q的**[mid + 1**, r]区间内，此时更新查找区间[l, r]为**[mid + 1, r]（即令l=mid+1）**
    2. 在新的查找区间内重复步骤1以进一步缩小查找区间，直到查找区间长度为0（区间两端坐标相同），该坐标点的数即为查找目标

在实际应用时，可直接根据选定的性质（check() = true）自行判断迭代条件为何种情况，再根据迭代条件判断属于以上哪种查找方式，使用对应的代码模板。

例题：789. 数的范围 - AcWing题库

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式

共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

1≤n≤100000
1≤q≤10000
1≤k≤10000

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
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &q[i]);
    
    while (m -- )
    {
        int x;
        scanf("%d", &x);
        
        //查找左边界
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (q[mid] >= x) //性质条件的选择：需要注意数组中可能含有多个相同数值（有序数列中连续排列）
                r = mid;
            else
                l = mid + 1;
        }
        
        //不存在该元素的判断：若数组中不存在指定的查找元素，该算法会输出数组中所有大于指定查找元素的数中的最小值，该值必然不等于指定查找元素
        if (q[l] != x) 
            cout << "-1 -1" << endl;
        else
        {
            cout << l << ' ';
            
            //查找右边界
            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = (l + r + 1) / 2;
                if (q[mid] <= x) //性质条件的选择：需要注意数组中可能含有多个相同数值（有序数列中连续排列）
                    l = mid;
                else
                    r = mid - 1;
            }
            
            cout << r << endl;
        }
    }
    
    return 0;
}

浮点数二分

基本思想：在实数轴上的一区间[l, r]中寻找某一浮点数x，可以对区间[l, r]进行若干次对半分割，保证所寻找的数始终位于保留的一半区间内；当保留的区间长度小于某个阈值（如10^(-6)）时，可以将区间的左边界看作查找目标浮点数x的近似值。

例题：

给定一个浮点数 n，求它的平方根。

输入格式

共一行，包含一个浮点数 n。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

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
#include <iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;
    
    double l = 0, r = x;
    
    while (r - l > 1e-8) //经验参数：误差限设置比题目要求的保留位数高两个数量级
    //也可直接指定迭代次数（如100次）for (int i = 0; i < 100; i ++ )
    {
        double mid = (l + r) / 2;
        if (mid * mid >= x) //注意：仅当x≥1或-1≤x≤0时可以将条件设置为大于等于
            r = mid;
        else
            l = mid;
    }
    
    printf("%lf\n", l);
    
    return 0;
}

高精度（C++）

针对于大整数（数字位数在10^6数量级）四则运算情形，C++没有内置的处理方案。

大整数的存储方式：数字各数位存入数组（从个位开始依次逆序存入，如数1145141919810存入数组[0,1,8,9,1,9,1,4,1,5,4,1,1]）

两个大整数相加

原理：模拟人工加法

例题：791. 高精度加法 - AcWing题库

给定两个正整数（不含前导 0），计算它们的和。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的和。

数据范围

1≤整数长度≤100000

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
#include <iostream>
#include <vector>

using namespace std;
    
// C = A + B
vector<int> add(vector<int> &A, vector<int> &B) // 加引用是为了提高效率，不加引用会把数据先拷贝一遍
{
    vector<int> C;
    
    int t = 0; // 用于存储两数在同一位数上的和，并保留进位
    for (int i = 0; i < A.size() || i < B.size(); i ++ )
    {
        if (i < A.size())
            t += A[i];
        if (i < B.size())
            t += B[i];
        C.push_back(t % 10);
        t /= 10;  
    }
    
    if (t)
        C.push_back(1);
    
    return C;    
}

int main()
{
    string a, b;
    vector<int> A, B;
    
    cin >> a >> b; // a = "123456"
    // 将读入的大整数（字符串形式）以各数位数字形式逆序存入数组，便于数位增减
    for (int i = a.size() - 1; i >= 0; i -- )
        A.push_back(a[i] - '0'); // A = [6, 5, 4, 3, 2, 1];
    for (int i = b.size() - 1; i >= 0; i -- )
        B.push_back(b[i] - '0');
    
    auto C = add(A, B); //auto:让编译器自主推断数据类型
    
    // 将相加后得到向量逆序输出
    for (int i = C.size() - 1; i >=0; i -- )
        cout << C[i];
      
    return 0;
}

两个大整数相减

原理：模拟人工减法

假定被减数大于等于减数（且均为正数），若减数大于被减数，则执行减数减去被减数再加上负号

若进行有负数的加减法，可以通过判断符号相互关系来转化成两者的绝对值相加或相减再添上符号的过程（分情况讨论即可），因此只要掌握正大整数的相加相减即可解决

对于某一第i位的对应数字相减A_i-B_i-t（t为后一位相减的借位0或1）而言：

  • 若A_i-B_i-t≥0：相减后结果为A_i-B_i-t
  • 若A_i-B_i-t<0：相减后结果为A_i-B_i+10-t

例题：792. 高精度减法 - AcWing题库

给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的差。

数据范围

1≤整数长度≤10^5

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
#include <iostream>
#include <vector>

using namespace std;
    
// 判断是否有 A >= B
bool cmp(vector<int> &A, vector<int> &B)
{
    // 若位数不同，只要判断位数的大小即可
    if (A.size() != B.size())
        return A.size() > B.size();
        
    // 若位数相同，从最高位开始依次比较各数位大小
    for (int i = A.size() - 1; i >= 0; i -- )
        if (A[i] != B[i])
            return A[i] > B[i];
    return true;      
}

// C = A - B
vector<int> sub(vector<int> &A, vector<int> &B) // 加引用是为了提高效率，不加引用会把数据先拷贝一遍
{
    vector<int> C;
    
    int t = 0; // 借位标志
    for (int i = 0; i < A.size() || i < B.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) // 通过比较大小已确定A.size() >= B.size()
            t -= B[i];
        C.push_back((t + 10) % 10); // 若t≥0，返回仍然为t;若t<0，返回t+10。这种写法是对两种情况的综合
        if (t < 0)
            t = 1;
        else
            t = 0;
    }
    
    // 去除有效位前面的空余零位（即前导0）
    while (C.size() > 1 && C.back() == 0) // 去掉数组中（倒序存入）中从最后一个开始数（即从最高位开始）为0的全部数，直到某一处不为0时停止；C.size() > 1：整个数只有一位且为0时不去除
        C.pop_back();
        
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    
    cin >> a >> b; // a = "123456"
    // 将读入的大整数（字符串形式）以各数位数字形式逆序存入数组，便于数位增减
    for (int i = a.size() - 1; i >= 0; i -- )
        A.push_back(a[i] - '0'); // A = [6, 5, 4, 3, 2, 1];
    for (int i = b.size() - 1; i >= 0; i -- )
        B.push_back(b[i] - '0');
    
    if (cmp(A, B))
    {
        auto C = sub(A, B); //auto:让编译器自主推断数据类型
    
        // 将相加后得到向量逆序输出
        for (int i = C.size() - 1; i >=0; i -- )
            cout << C[i];
        
    }
    else
    {
        auto C = sub(B, A);
        
        cout << "-";
        for (int i = C.size() - 1; i >=0; i -- )
            cout << C[i];
	}
      
    return 0;
}

大整数与小范围整数相乘

基本思想：用大数的各位（从低位到高位）依次直接与小数整体相乘，依照进位法则得到结果的各位数

例题：793. 高精度乘法 - AcWing题库

给定两个非负整数（不含前导 0） A 和 B，请你计算 A×B 的值。

输入格式

共两行，第一行包含整数 A，第二行包含整数 B。

输出格式

共一行，包含 A×B 的值。

数据范围

1≤A的长度≤100000, 0≤B≤10000

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
#include <iostream>
#include <vector>

using namespace std;

// C = A * b
vector<int> mul(vector<int> &A, int b) 
{
    vector<int> C;
    
    int t = 0; // 借位标志
    for (int i = 0; i < A.size() || t != 0; i ++ ) // 循环截止条件：大数各数位均完成相乘且进位完成
    {
        if (i < A.size()) // 若大数各数位还未遍历相乘完成，则执行相乘并将进位项加入
            t += A[i] * b;
        C.push_back(t % 10);
        t /= 10; // 进位 
    }
    
    // 去除有效位前面的空余零位（即前导0）
    while (C.size() > 1 && C.back() == 0) // 去掉数组中（倒序存入）中从最后一个开始数（即从最高位开始）为0的全部数，直到某一处不为0时停止；C.size() > 1：整个数只有一位且为0时不去除
        C.pop_back();
        
    return C;
}

int main()
{
    string a;
    int b;
    vector<int> A;
    
    cin >> a >> b; 
    // 将读入的大整数（字符串形式）以各数位数字形式逆序存入数组，便于数位增减
    for (int i = a.size() - 1; i >= 0; i -- )
        A.push_back(a[i] - '0'); 
    
    auto C = mul(A, b);
    
    for (int i = C.size() - 1; i >=0; i -- )
            cout << C[i];
      
    return 0;
}

大整数除以小范围整数

基本思想：用大数的各位（从高位到低位）依次直接除以小数整体，不断作商与保留余数，得到商的各位数以及最终剩下的余数

例题：794. 高精度除法 - AcWing题库

给定两个非负整数（不含前导 0） A，B，请你计算 A/B 的商和余数。

输入格式

共两行，第一行包含整数 A，第二行包含整数 B。

输出格式

共两行，第一行输出所求的商，第二行输出所求余数。

数据范围

1≤A的长度≤100000, 1≤B≤10000, B 一定不为 0

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>
#include <vector>
#include <algorithm>

using namespace std;

// A / b, 商是C, 余数是r
vector<int> div(vector<int> &A, int b, int &r) // 余数r通过引用传回
{
    vector<int> C; // 商
    r = 0;

    for (int i = A.size() - 1; i >= 0; i -- ) // 从最高位开始算
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b; 
    }
    
    reverse(C.begin(), C.end()); //除法过程中商由高位到低位依次存入向量C，需调用头文件<algorithm>中的reverse方法对向量进行逆序处理后再去除前导0
    
    // 去除有效位前面的空余零位（即前导0）
    while (C.size() > 1 && C.back() == 0) // 去掉数组中（倒序存入）中从最后一个开始数（即从最高位开始）为0的全部数，直到某一处不为0时停止；C.size() > 1：整个数只有一位且为0时不去除
        C.pop_back();
        
    return C;
}

int main()
{
    string a;
    int b;
    vector<int> A;
    
    cin >> a >> b; 
    // 将读入的大整数（字符串形式）以各数位数字形式逆序存入数组，便于数位增减
    for (int i = a.size() - 1; i >= 0; i -- )
        A.push_back(a[i] - '0'); 
    
    int r; // 余数
    auto C = div(A, b, r);
    
    for (int i = C.size() - 1; i >=0; i -- )
        cout << C[i];
    cout << endl << r << endl;
      
    return 0;
}

前缀和

一维前缀和

对一个n项数组A：a_1、a_2、a_3、…、a_n，定义其前缀和（数组A中前i个数的和）【注意下标从1开始】
$$
S_i=a_1+a_2+…+a_i
$$

  1. 如何求前缀和S_i？

    通过前缀和数组S_i中的前一项加上原数组A中的该项得到；注意需初始化S[0]=0。

    1
    2
    for (int i = 1; i <= n; i ++ )
        S[i] = S[i - 1] + A[i - 1]; // A[i - 1] = a_i

  2. 前缀和数组的作用？

    快速求出原数组A中一段数的和：将时间复杂度由O(n)降低到O(1)
    $$
    a_l + a_{l+1} + a_{l+2} + … + a_r = S_r - S_{l-1}
    $$

例题：795. 前缀和 - AcWing题库

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式

共 m 行，每行输出一个询问的结果。

数据范围

1≤l≤r≤n, 1≤n,m≤100000, −1000≤数列中元素的值≤1000

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
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int A[N], S[N];

int main()
{
    scanf("%d%d", &n, &m); // 数据规模较大，用scanf读取输入数据
    // 若想使用cin读取输入数据，需要添加下列代码提高cin读取速度（作用是取消与标准读入scanf同步，但提高后仍然没有scanf快）；添加后的副作用是无法再使用scanf
    // ios::sync_with_stdio(false);
    // 数据输入规模≥1000000时建议用scanf，否则用cin即可
    for (int i = 0; i < n; i ++ )
        scanf("%d", &A[i]);
    
    for (int i = 1; i <= n; i ++ )
        S[i] = S[i - 1] + A[i - 1]; // 前缀和初始化
    
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", S[r] - S[l - 1]); // 区间和计算
    }
      
    return 0;
}

二维前缀和

用途：快速求子矩阵各元素之和

基本思想：容斥原理

对于矩阵A而言，其中各元素为a_ij，则S_ij代表矩阵中该元素左上角所有元素的和（包含i行与j列）

S_nm的计算：

1
2
3
for (int i = 1; i <= n; i ++ )
	for (int j = 1; j <= m; j ++ )
		S[i][j] = A[i - 1][j - 1] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]; // A[i - 1][j - 1] = a_ij

对于A中的一个子矩阵（左上顶点坐标(x1, y1)，右下顶点坐标(x2, y2)），其各元素和计算公式为：
$$
Sum=S_{x_2 y_2}-S_{(x_1-1) y_2}-S_{x_2 (y_1-1)}+S_{(x_1-1) (y_1-1)}
$$

例题：796. 子矩阵的和 - AcWing题库

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问，输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 n，m，q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式

共 q 行，每行输出一个询问的结果。

数据范围

1≤n,m≤1000, 1≤q≤200000, 1≤x1≤x2≤n, 1≤y1≤y2≤m, −1000≤矩阵内元素的值≤1000

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 <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int A[N][N], S[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q); 
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
        	scanf("%d", &A[i][j]);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            S[i][j] = A[i - 1][j - 1] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]; // 求前缀和
    
    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]); // 计算子矩阵的和
    }
      
    return 0;
}

差分

一维差分

前缀和的逆运算

对一个n项数组A：a_1、a_2、a_3、…、a_n，构造数组B：b_1、b_2、b_3、…、b_n，使得：(数组A为数组B的前缀和)
$$
a_i=b_1+b_2+…+b_i
$$
一维构造方法（用不上）：
$$
b_1=a_1\
b_2=a_2-a_1\
b_3=a_3-a_2\
……\
b_n=a_n-a_{n-1}
$$
此时称B数组为A数组的差分。

显然，若已有数组B，可以用O(n)的时间通过计算前缀和的方式得到数组A。

用途：如果希望使得数组A中某一区间[l, r]内的所有元素都加上一个常数c，可以通过差分方法将原本的时间复杂度O(n)降低到O(1)

实现方式：对于数组A的差分数组B，同样在区间[l, r]上：只要让b_l加上c，即可实现数组A中位置l及其以后的所有数都加上c；作为补偿，只要让b_{r+1}减去c，即可实现数组A中的元素仅在区间[l, r]上加上常数c。

注意：若在初始时将数组A中的所有元素视为0，那么显然此时B中的所有元素也都是0；但事实上并非如此，那么可以将数组A视为由同等长度的全零数组经过若干次【在某区间（区间长度可为1）内加上某常数】操作得到，藉此也可得到对应的差分数组B。

也因此，我们在构造差分数组的时候并不关心如何由原数组构造而来，而是通过对全零数组进行插入变换得到原数组A的过程来得到差分数组B

例题：797. 差分 - AcWing题库

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 l,r 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数序列。

接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。

输出格式

共一行，包含 n 个整数，表示最终序列。

数据范围

1≤n,m≤100000, 1≤l≤r≤n, −1000≤c≤1000, −1000≤整数序列中元素的值≤1000

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
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

// 插入函数insert：将数组a在[l, r]区间内的所有元素加上常数c，差分数组b产生的变化
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    // 注意：下标均从1开始，因为求前缀和要求a[0]=0
    
    scanf("%d%d", &n, &m); 
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]);
  
    for (int i = 1; i <= n; i ++ )
        insert(i, i, a[i]);
    
    while (m -- )
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    
    // 对差分数组b求其前缀和得到输出数组a(插入后)
    for (int i = 1; i <= n; i ++ )
        b[i] += b[i - 1];
    
    for (int i = 1; i <= n; i ++ )
        printf("%d ", b[i]);
      
    return 0;
}

二维差分

用途：对矩阵中的某个子矩阵中的所有元素加上常数c

与一维差分不同的是：基于容斥原理，若要在原矩阵A中对于以a_ {x1y1}（下标从1开始）为左上顶点、以a_ {x2y2}为右下顶点的子矩阵区域中的所有元素加上常数c，需要对差分矩阵b做如下处理：

1
2
3
4
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;

例题：798. 差分矩阵 - AcWing题库

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数 n,m,q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。

输出格式

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

1≤n,m≤1000, 1≤q≤100000, 1≤x1≤x2≤n, 1≤y1≤y2≤m, −1000≤c≤1000, −1000≤矩阵内元素的值≤1000

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
#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

// 插入函数insert：将矩阵a在以a_{x1y1}（下标从1开始）为左上顶点、以a_{x2y2}为右下顶点的子矩阵区域中的所有元素加上常数c，差分数组b产生的变化
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q); 
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        	scanf("%d", &a[i][j]);
  
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);
    
    while (q -- )
    {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    
    // 对差分数组b求其前缀和得到输出数组a(插入后)
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        	b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        	printf("%d ", b[i][j]);
        cout << endl;
    }
      
    return 0;
}

双指针算法

算法的应用场景和具体形式有很多，并不局限于某一类问题，如快速排序/归并排序/KMP……

常用的双指针算法有两类：

  • 在两个序列中，一个指针指向其中一个序列，另一个指针指向另一个序列，用于维护某种次序【e.g. 归并排序中的归并】
  • 两个指针指向同一个序列中的不同位置（维护两个指针之间的一段区间）【e.g. 快速排序中的数组划分】

核心思想：对二层循环的情景而言，利用某些性质（如归并排序中利用已有序序列的单调性），将暴力循环遍历枚举（朴素算法）的时间复杂度O(n^2)降低到O(n)

基本代码结构：

1
2
3
4
5
6
7
8
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) // j随i的更新而更新的条件：j的范围 + 满足某种性质
        j ++ ;
    
    // 每道题目的具体逻辑
    
}

一般做法：先写出朴素算法思路，若涉及二重嵌套循环且循环指针i、j间存在单调关系（如i↑，j↑）则可考虑采用双指针算法进行优化

例题：

给定一个英文字符串，其中包含若干个单词，单词之间由一个空格隔开，输出各个单词。

输入格式

共一行，包含一个字符串。

输出格式

输出若干行，每行仅包含字符串中的一个单词。

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
#include <iostream>
#include <string.h>

using namespace std;

int main()
{
    char str[1000];
    
    gets(str);
    
    int n = strlen(str); // 字符串长度
    
    for (int i = 0; i < n; i ++ )
    {
        int j = i;
        // 想用j从一个单词的开头一直指到该单词末尾
        while (j < n && str[j] != ' ')
            j ++ ;
        
        // 问题具体逻辑
        for (int k = i; k < j; k ++ )
            cout << str[k];
        cout << endl;
        
        i = j + 1;
    }
    
    return 0;
}

例题：799. 最长连续不重复子序列 - AcWing题库

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 n。

第二行包含 n 个整数（均在 0∼10^5 范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围

1≤n≤10^5

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
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N], s[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        cin >> a[i];
    
    int res = 0;
    
    // 朴素做法：O(n^2)
    // for (int i = 0; i < n; i ++ )
    //     for (int j = 0; j <= i; j ++ )
    //         if (check(j, i))
    //             res = max(res, i - j + 1);
    
    // 继承朴素算法的思路：将i视为目标子序列的终点，j从数组起点开始向i位置移动，判断区间[j,i]上的子序列是否满足不重复条件，并保留满足该条件的最长区间的长度
    // 注意：随着i的增大，显然其对应满足不重复条件的最小j值（区间最长）也在增大（或不变）【指针j具有单调性】；指针i与j之间相互独立
    // 该算法可保证指针i、j各自总共最多走n步，两者相加即总步数不超过2n，时间复杂度为O(n)
    for (int i = 0, j = 0; i < n; i ++ )
    {
        // 在判断目标区间中是否含有重复元素时，由于本题的数据范围在0~10^5较小，可以开辟一个新数组s，其各项可以存储对应位置在目标区间内的数据个数; 显然若含有重复元素，则必然为新加入的数据a[i]，因此可以通过其数量（1或2）判断新区间内是否含有重复元素
        // 若数据范围较大/求字母序列，可以采用哈希表代替数组用于存储数量
        s[a[i]] ++ ;
        while (j <= i && s[a[i]] != 1)
        {
            // 注意：若要将j指针后移，需先把当前j位置的数在区间内的数量减去1
            s[a[j]] -- ;
            j ++ ;
        }
        
        res = max(res, i - j + 1);        
    }
    
    cout << res;
          
    return 0;
}

位运算

首先需要指出，c++中的int存储时以二进制形式存储（如10的二进制为1010）

基本位运算（对于int类型的数据，直接对其二进制形式进行位操作）：

  • 右移运算>>：将二进制数整体向右（个位方向）移动，如n>>k说明将二进制数n向右移动k位，超出个位的部分直接舍去
  • 与运算&：以a&b为例，将b的各位数字与a的各位数字作与运算（同时为1返回1，否则返回0），并将各位与运算的结果作为整体运算结果的各位（仅保留a与b中位数较少的位数）【或/并运算同理，按位运算】
  • 取反运算~：原二进制各数位取反（0变1，1变0）

常用两种操作：

  • 数字n的二进制表示中的第k位数字是几（个位是第0位）—— (n >> k) & 1
    1. 先把第k位移到个位：采用右移运算n >> k
    2. 看当前个位是几 ：取右移后的二进制数x的个位x&1
  • lowbit：树状数组的基本操作
    • lowbit(x)的作用：返回x的最后一位1（为1的最低位及后面所有为0的位，如lowbit(101000)=1000）
    • lowbit函数的实现：lowbit(x) = x & -x = x & (x + 1)【c++补码：-x=x+1（~为取反符号）】
    • 应用：统计二进制数x中1的个数（每次取lowbit之后减去lowbit的返回值，多次重复这个过程直至减去后为0，这个过程重复了几次就有几位1）

例题：801. 二进制中1的个数 - AcWing题库

给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。

输入格式

第一行包含整数 n。

第二行包含 n 个整数，表示整个数列。

输出格式

共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

数据范围

1≤n≤100000, 0≤数列中元素的值≤10^9

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
#include <iostream>
 
using namespace std;

int lowbit(int x)
{
	return x & -x;
}

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

    while (n -- )
    {
        int x;
        cin >> x;

        int res = 0;
        while (x != 0)
        {
            x -= lowbit(x); // 每次减去x的最后一位1
            res ++ ;
        }
        
        cout << res << " ";
    }
    
    return 0;
}

离散化

特指整数的、保序（小的仍小、大的仍大）的离散化。

基本含义：数组的映射

e.g. 这类问题通常会研究一个有序数组a[]，其中数值的值域在0~10^9，数组长度不超过10^5【数组值域跨度大，但分布稀疏】；若想统计各元素数值在数组中出现的个数，需要新开一个数组b[]用于存储，其以数组a[]中各元素数值作为下标，数组b[]在该下标处的数值即为其在数组a[]中出现的次数；但此时值域过大，由于内存限制开不了这么长的数组，因此需要将原数组映射到一个新的数组中以缩小值域范围（通常映射至其下标）

问题：

  • 数组a[]中可能有重复元素——去重
1
2
3
vector<int> a; // 目标数组a
sort(a.begin(), a.end()); // 对数组a排序
a.erase(unique(a.begin(), a.end()), a.end()); // 去除重复元素（unique负责把数组中的重复元素移到向量的末尾，并返回重复元素的存储起点；在使用erase方法将重复元素的存储区间删除）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// unique函数的实现
// 基本思路：双指针算法
// 将原数组中满足unique条件的数放入输出的数组以确保输出数组中无重复元素，unique条件：（针对有序数组）a[0]或a[i] != a[i - 1]
vector<int>::iterator unique(vector<int> &a)
{
    for (int i = 0, j = 0; i < a.size(); i ++ )
        if (i ==0 || a[i] != a[i - 1])
            a[j ++ ] = a[i];
    // a[0] ~ a[j - 1]为a中所有不重复的数
    
    return a.begin() + j;
}

// 用法
a.erase(unique(a), a.end());
  • 如何算出数组中元素值x离散化后的值（该元素的下标）——二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = a.size() - 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (a[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return r + 1; // 是否+1与题目有关，若+1则从1开始映射（映射到[1, 2, ..., n]）
}

例题：802. 区间和 - AcWing题库

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r]之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式

共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围

−10^9≤x≤10^9, 1≤n,m≤10^5, −10^9≤l≤r≤10^9, −10000≤c≤10000

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 300010; // 虽然题目中数据范围为100000，但离散化后实际上最多会有300000个不同的数【插入操作100000次（在100000个不同坐标）、查询操作100000次（每次查询会涉及区间开端末尾2个坐标）】

int n, m;
int a[N], s[N]; // a[]为离散化后数组，s[]为前缀和数组

typedef pair<int, int> PII; // n次操作，用pair数据类型进行存储

vector<int> alls; // 离散化前存储原数组
vector<PII> add, query;

int find(int x) // 求x值离散化后结果（映射至下标数组）
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (alls[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return r + 1; // 后续需要使用前缀和，故将原数组映射到以1为起点的下标数组
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        
        alls.push_back(x);
    }
    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        
        alls.push_back(l);
        alls.push_back(r);
    }
        
    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    
    // 处理插入
    for (auto item : add)
    {
        int x = find(item.first);
        a[x] += item.second; // 在离散化后的（下标数组）坐标位置加上所需加上的数
    }
    
    // 前缀和预处理
    for (int i = 1; i <= alls.size(); i ++ )
        s[i] = s[i - 1] + a[i];
    
    // 处理询问
    for (auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl; 
    }
    
    return 0;
}

区间合并

应用场景：快速对提供的n个区间中有交集的区间进行合并

【规定：若两个区间仅端点相交也合并】

步骤：

  1. 按区间左端点大小对各区间进行排序

  2. 先锚定（从排序后的第一个区间开始）一个维护区间[op, ed]，随后对剩余的区间依次进行扫描，若当前扫描到的区间为[op’, ed’]，两个区间之间的关系可能如下：

    • 扫描区间在维护区间内(op≤op’且ed’≤ed）->[op, ed]
    • 两个区间有交集（由于已经过排序，交集部分只可能在维护区间左侧、扫描区间右侧）(op≤op’且ed≤ed’）->[op, ed’] (ed = ed’)
    • 两个区间无交集（由于已经过排序，扫描区间完全位于维护区间右侧）(ed≤op’）->将当前维护区间[op, ed]放入已完成合并的答案中，转而将扫描区间[op’, ed’]作为新的维护区间

    直到扫描完全部的区间并将最后一个维护区间放入答案中，合并完成。

与区间相关的问题，大多采用贪心的思想解决（按照区间左端点/右端点/两侧端点双关键字进行排序）

例题：803. 区间合并 - AcWing题库

给定 n 个区间 [l_i,r_i]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1 ≤ n ≤ 100000, −10^9 ≤ l_i ≤ r_i ≤ 10^9

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
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII; // 用pair数据类型存储区间的两个端点，first存的是区间的左端点，second存的是区间的右端点

const int N = 100010;

int n;
vector<PII> segs; // 用vector存储区间端点对

void merge(vector<PII> &segs)
{
    vector<PII> res;
    
    sort(segs.begin(), segs.end()); //c++中对pair数据类型排序，会默认优先按照左端点first进行排序，对于左端点相同的元素再按照右端点second进行排序
    
    int op = -2e9, ed = -2e9; // 初始化起始区间为[-2e9, -2e9]（实际上初始化起始区间为segs中的第一个也可以，后面代码需要对应修改）
    for (auto seg : segs)
    {
        if (ed < seg.first) // 无交集
        {
            if (op != -2e9) // 起始区间[-2e9, -2e9]不在提供的数组中，不放入答案
                res.push_back({op, ed});
            op = seg.first;
            ed = seg.second;
        }
        else // 有交集
            ed = max(ed, seg.second); // 兼容包含与相交两种情况
    }
    
    if (op != -2e9) // 防止输入的vector中没有任何pair
        res.push_back({op, ed});
    
    segs = res;
}

int main()
{
    cin >> n;
    
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    
    merge(segs);
    
    cout << segs.size() << endl;
        
    return 0;
}

第一章 基础算法

http://asgard-tim.github.io/2025/03/30/第一章 基础算法/

作者

Tim

发布于

2025-03-30

更新于

2025-04-29

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

关注我

最新文章

分类

归档

标签

3D-VLA1
ADS12921
Arduino1
Buck变换器1
C++4
C511
COMSOL1
ChatGPT1
FIR1
FPGA1
FreeRTOS1
IIR1
Linux1
Logistic回归1
MATLAB3
Matlab3
PID闭环控制1
Python3
QQbot1
RANSAC1
ROS1
Robotics Transformer1
R语言1
STM324
Shewhart控制图1
Ubuntu1
Unity1
VLA2
XJH1
乘幂法1
二分类1
产品质量管理1
人机交互1
传热学1
信号与系统2
假设检验1
傅里叶变换1
光伏MPPT1
具身智能2
动力学仿真2
动手学深度学习2
单片机5
卷积神经网络1
双三次插值1
双线性插值1
可视化1
四平面插值1
图像插值1
图像放大1
图像旋转1
图像识别1
多模态大模型2
学习笔记2
定量分析1
小车2
工程热力学1
心电信号采集1
快速截断Huber损失1
扩散方程1
支持向量机1
救灾机器人1
数值迭代求解1
数字信号处理1
数据处理分析1
斯特林发动机4
斯特林循环2
最近邻插值1
有限元仿真1
本征值求解1
机器学习2
机械臂1
机械设计1
柔性套索惩罚1
滤波器1
烟雾扩散1
电机控制1
矩阵特征值1
算法与数据结构2
线性代数1
统计过程控制1
自动控制原理1
自动调光1
自编码器1
船1
计算机视觉1
设计思维1
距离特性1
路径规划1
闭环控制1
频谱分析2
高斯核函数1
×