前言

本文记录算法竞赛备赛过程中所使用的基础算法，其中包括排序，差分，高精度运算等。一是为了准备蓝桥，二是读研时的机试，以及数据结构与算法方面的知识

排序

需注意边界问题

快速排序

  1. 确定分界点
  2. 调整区间，使x左边的区间都小于等于x（此时区间内不一定是有序的），右边则大于
  3. 递归处理左右两段
1
2
3
4
5
6
7
8
9
10
11
void quick_sort(int q[], int l, int r) {
    if (l >= r) return; 
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j+1, r);
}

Acwing785.快速排序

快速选择算法(第K小的元素)

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 <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int q[N];

int quick_sort(int q[], int l, int r, int k) {
    if (l == r) return q[l];
    int x = q[l+r>>1], i = l-1, j = r + 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 sl = j - l + 1; // 代表比x小的区间内数的个数
    // 若k小于等于sl，说明要找的数在左半区间
    if (k <= sl) return quick_sort(q, l, j, k); 
    // 反之，在右半区间，这时要寻找的数要减去左半区间的长度
    else return quick_sort(q, j + 1, r, k - sl);
}
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    cout << quick_sort(q, 0, n-1, k) << endl;
    return 0;
}

归并排序

  1. 确定分界点为首末中点
  2. 以中点为界，递归排序中点两侧使其有序
  3. 归并，合二为一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void merge_sort(int q[], int l, int r) {
    if (l >= r) return;
    // 拆分过程
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid+1, r);
    // 合并两个有序序列
    int k = 0, i = l, j = mid+1;
    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]; 
}

Acwing787.归并排序

逆序对的数量

在使用归并排序求解逆序对的数量时

我们将序列从中间分开，将逆序对分成三类：

  • 两个元素都在左边（递归）；
  • 两个元素都在右边（递归）；
  • 计算两个元素一个在左一个在右；

如果一个左边的数与右边的数构成逆序对时，那么左边剩余的数，均是右边数的逆序对

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
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int q[N], temp[N];
int n;
LL res = 0;

void merge_sort(int q[], int l, int r) {
    if (l >= r) return;
    
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid+1, r);
    
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) temp[k++] = q[i++];
        else {
            temp[k++] = q[j++];
            res += mid - i + 1;
        }
    }
    while (i <= mid) temp[k++] = q[i++];
    while (j <= r) temp[k++] = q[j++];
    
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
}

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

二分

当题目具有二段性或者单调性（也可以没有）时，可以采用二分进行枚举查找

整数

版本一

边界点归于左半边，从而将[l, r]拆分成[l, mid]和[mid+1, r]

1
2
3
4
5
6
7
8
9
10
11
int l = 0, r = n-1;
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本二

边界点归于右半边，从而将[l, r]拆分成[l, mid-1]和[mid, r]

注意，在取mid时要加1

1
2
3
4
5
6
7
8
9
10
11
int l = 0, r = n-1;
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

Acwing789.数的范围

整数二分-机器人跳跃问题

浮点数

相较于整数不用考虑边界的加一减一问题

保留4位小数，则保留精度到1e-6；保留6位小数，则保留精度到1e-8

1
2
3
4
5
6
double l = 0, r = x;
while (r - l > 1e-8) {
    double mid = (l+r) / 2;
    if (mid * mid >= x) r = mid;
    else l = mid;
}

大整数运算

高精度整数，指用基本数据类型无法存储其精度的整数。

大整数的存储：整数的高位存储在数组的高位，整数的低位存储在数组的低位。因此由于进位的缘故，我们需要将整数逆序的读入vector容器当中，读入时需要注意反转。

由于在C++中没有处理大整数的类，我们需要用字符串string，来处理大整数的加减乘除

高精度加法

模拟人工计算，从末位开始加减，用取余的方式进行进位。如果最后还有余数，则最后一位需进1

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

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    
    int t = 0; // t同时代表进位、进位加和
    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; // 十位为新的进位
    }
    
    // 如果最后一位进位不为0，则直接赋给结果的最高位
    if (t) C.push_back(1);
    
    return C;
}

int main() {
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    
    return 0;
}

高精度减法

  • 主要的难点在于借位与进位，(t + 10) % 10巧妙地解决了借位的情况，为正数时，加10模10仍为本身；为负数时，则满足了减法规则。
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
#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; // 两者相等
}

// A-B，在A>=B的前提下
vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;
    
    for (int i = 0, t = 0; i < A.size(); i++) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10); //巧妙解决借位下的计算
        if (t < 0) t = 1;
        else t = 0;
    }
    
    // 避免出现类似001的情况
    while (C.size() > 1 && C.back() == 0) C.pop_back(); //去掉前导0
    
    return C;
}

int main() {
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    
    // 判断A>=B
    if (cmp(A, B)) {
        auto C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    } else {
        auto C = sub(B, A);
        printf("-");
        for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    }
    
    return 0;
}

高精度乘法

  • 注意如t还未变为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
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> A, int b) {
    vector<int> C;
    
    int t = 0;
    for (int i = 0; i < A.size() || t; i++) { // t中可能仍存在进位
        if (i < A.size()) t = A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    
    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--) printf("%d", C[i]);
    
    return 0;
}

高精度除法

区别于其它三种运算是从低位开始计算，除法是从高位开始

  • 余数需要同时传入r的引用
  • C最后要进行一次倒置，来保证与其它四则运算输出兼容
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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// A / b，余数r，商为C
vector<int> div(vector<int> &A, int b, int& 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());
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}


int main() {
    string a;
    int b;
    cin >> a >> b;
    
    vector<int> A;
    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--) printf("%d", C[i]);
    cout << endl << r << endl;
    
    return 0;
}

前缀和

一维

前缀和指数列中前n个数的和（1 < n < 数列长度），利用前缀和可以求出数列任一区间内数的和

本质是高中数列的一个知识点ai = S(i) - S(i-1)

  • a[1],a[2],...,a[n]a[1],a[2],...,a[n]

  • s[i]=a[1]+a[2]+...+a[i]s[i] = a[1]+a[2]+...+a[i]

这也体现出了算法题不过于数学思想的一种体现，不会数学的确也可以写代码，但肯定不能写好代码

我们计算机专业的同学学习专业课的同时，也不可忽视数学的学习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main() {
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) s[i] = s[i-1] + a[i]; // 初始化一维前缀和
    
    while (m -- ) {
        int l, r;
        scanf("%d%d", &l, &r);
        // 计算任一区间和
        printf("%d\n", s[r] - s[l-1]);
    }
    return 0;
}

二维

由一维前缀和拓展而来，二维平面内的每一个点的值s[i][j]代表其左上方值之和；

image-20220314125945974

求前缀和计算公式为，（DP思想，利用前两个点求）

s[i][j]=s[i−1][j]+s[i][j−1]−s[i−1][j−1]+a[i][j]s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

image-20220314151427297

由此，我们可以计算任一面积内的点数之和，

s[i][j]−s[i−1][j]−s[i][j−1]+s[i−1][j−1]s[i][j]-s[i-1][j]-s[i][j-1]+s[i-1][j-1]

image-20220314130420871 
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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
int g[N][N];

int main() {
    int N, R;
    cin >> N >> R;
    int n = R, m = R;
    for (int i = 0; i < N; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x++, y++; // 前缀和习惯从下标1开始
        g[x][y] += w;
        n = max(n, x), m = max(m, y);
    }
    for (int i = 1; i <= 5001; i++) 
        for (int j = 1; j <= 5001; j++) 
            g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];
    int ans = 0;
    if (R >= 5000) {
        cout << g[5001][5001] << endl;
        return 0;
    }
    for (int i = R; i <= 5001; i++) {
        for (int j = R; j <= 5001; j++) {
            ans = max(ans, g[i][j] - g[i-R][j] - g[i][j-R] + g[i-R][j-R]);
        }
    }
    cout << ans << endl;
    return 0;
}

HNOI2003.激光炸弹（二维前缀和）

差分

与前缀和互为逆运算

创建一数组b，使得数组a为数组b的前缀和，数组b为数组a的差分

构造方法：b[i] = a[i] - a[i - 1]

此处使用了一个虚拟的构造方式（在数组一个位置加上一个数，那么在它的下一个位置减去这一数）

应用：对于a数组的任意区间[l, r]，令其加上一个数，而不改变其它值

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
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
// 核心代码
void insert(int l, int r, int c) { 
    b[l] += c;
    b[r + 1] -= c;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    // 在数组一个位置加上一个数，那么在它的下一个位置减去这一数
    // 等同于b[i] = a[i] - a[i - 1]
    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);
        // 在[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;
}

AcWing797.差分

双指针算法

常用问题分类：

  1. 对于一个序列，用两个指针维护一段区间
  2. 对于两个序列，维护某种次序。比如归并排序中合并两个有序序列的操作

每个双指针算法都由一个朴素算法变化而来

1
2
3
4
5
6
// 朴素解法 时间复杂度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);
        }

关于双指针算法的时间复杂度为o(n)：

因为j只初始化了一次，且在过程中，j只增不减

1
2
3
4
5
// 双指针算法 时间复杂度o(n)
for (int i = 0, j = 0; i < n; i++) {
    while (j <= i && check(j, i)) j++;
    res = max(res, i - j + 1);
}

最长不重复子序列

序列不一定递增

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], s[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ ) {
        s[a[i]]++;
        while (s[a[i]] > 1) {
            s[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    
    return 0;
}

位运算

一个数的二进制表示

  1. 进行移位
  2. &1表示取出当前最后一位
1
2
3
4
5
6
7
8
#include <iostream>
using namespace std;
int main() {
    int n = 10;
    for (int k = 3; k >= 0; k--) 
        cout << (n >> k & 1) ; // 核心代码
    return 0;
}

一个数的二进制中1的个数

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

输入格式

第一行包含整数 nn。

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

1
2
5
1 2 3 4 5

输出格式

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

1
1 1 2 1 2

−x=( x+1)-x = (~x+1)

x &−xx \ \& -x 意味着取出最后一个1及其后面的数

x=1010001000x = 1010001000

$ \sim x = 0101110111$

−x=∼x+1=0101111000-x = \sim x+1 = 0101111000

x&−x=x&(∼x+1)=1000x \& -x = x \& (\sim x+1) = 1000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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) x -=lowbit(x), res++;
        cout << res << ' ';
    }
    
    return 0;
}

离散化

数的值域跨度范围很大，但数的个数很少，通常会差几个数量级

关于unique():

  • 使用前需排序
  • 所有不重复的元素排在数组的最前面，数组末尾未占用的位置保留原来的值
  • 返回值是不重复的元素个数（标准说法是去重之后的尾地址），即重复元素的第一位，便于erase对其进行删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 从小到大排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 序列去重

// 二分求出x对应离散化后的值
int find(int x) { // 找出第一个大于等于x的位置
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        // x在哪，区间就往哪里缩
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

区间和

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

−109≤x≤109−10^9≤x≤10^9,(离散化的原因)
1≤n,m≤1051≤n,m≤10^5,
−109≤l≤r≤109−10^9≤l≤r≤10^9,(离散化的原因)
−10000≤c≤10000−10000≤c≤10000

输入样例：

1
2
3
4
5
6
7
3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：

1
2
3
8
0
5

因为数的下标范围过大(10910^9)，我们无法开辟一个如此大的数组。

为此，我们将数的下标存储成值，来进行计算

开3∗1053*10^5的原因是总共数的个数，包括了n, 2m(l,r)， 它们为10510^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
#include <iostream>
#include <vector>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls; //存储所有的位置
vector<PII> add, query;
// 二分，将题目给的较大位置，映射成数组的下标
int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r+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) {
        a[find(item.x)] += item.y;
    }
    
    // 求其前缀和，以便求任意区间
    for (int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + a[i];
    // 处理问询结果
    for (auto t : query) {
        int l = find(t.x), r = find(t.y);
        cout << s[r] - s[l-1] << endl;
    }
    return 0;
}

unique()源码剖析

本质：双指针

作用：去重

条件：1）第一个元素 2）a[i] != a[i-1]

1
2
3
4
5
6
7
8
vector<int>::iterator unique(vector<int> &a) {
    int j = 0;
    for (int i = 0; i < a.size(); i++)
        if (!i || a[i] != a[i-1])
            a[j++] = a[i];
    
    return a.begin() + j;
}

区间合并

如果两个区间有交集，则将区间合并为一个

区间与区间之间的关系分为三类：

  1. 彼此互不相交
  2. 后一个区间被前一个区间包含
  3. 后一个区间与前一个有相交的部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void merge(vector<PII>& segs) {
    vector<PII> res;
    
    sort(segs.begin(), segs.end());
    
    int st = -2e9, ed = -2e9; // 维护一个区间
    for (auto seg: segs) {
        // 处理情况一
        // 新区间不在维护的区间范围内， 说明是一个全新的区间
        if (ed < seg.first) {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } else //处理情况二、三
            ed = max (ed, seg.second);
    }
    if (st != -2e9) res.push_back({st, ed});
    
    segs = res;
}

参考资料

Acwing算法基础课

这里强烈推荐y总的算法基础课！！！`