当前位置:   article > 正文

【算法竞赛备赛】基础算法_青少年算法竞赛必备算法

青少年算法竞赛必备算法

前言

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

排序

需注意边界问题

快速排序

  1. 确定分界点
  2. 调整区间,使x左边的区间都小于等于x(此时区间内不一定是有序的),右边则大于
  3. 递归处理左右两段
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);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

Acwing785.快速排序

归并排序

  1. 确定分界点为首末中点
  2. 以中点为界,递归排序中点两侧使其有序
  3. 归并,合二为一
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]; 
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

Acwing787.归并排序

二分

整数

版本一

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

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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

版本二

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

注意,在取mid时要加1

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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

Acwing789.数的范围

浮点数

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

保留4位小数,则保留精度到1e-6;保留6位小数,则保留精度到1e-8

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

高精度

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

加法

  • 大整数的存储:由于进位的缘故,我们需要将整数逆序的读入vector容器当中
  • 大整数的计算:模拟人工计算,从末位开始加减,用取余的方式进行进位。如果最后还有余数,则最后一位需进1
// big number
#include <iostream>
#include <vector>

using namespace std;


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;
    
    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;
}
  • 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

减法

  • 主要的难点在于借位与进位
#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');
    
    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;
}
  • 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

乘法

  • 注意如t还未变为0时,需要重复执行
#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++) {
        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;
}
  • 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

除法

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

前缀和

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

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

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

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

#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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

差分

与前缀和互为逆运算

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

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

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

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

#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;
}
  • 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

AcWing797.差分

双指针算法

常用问题分类:

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

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

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

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

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

// 双指针算法 时间复杂度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

最长不重复子序列

序列不一定递增

#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
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

位运算

一个数的二进制表示

  1. 进行移位
  2. &1表示取出当前最后一位
#include <iostream>
using namespace std;

int main() {
    int n = 10;
    
    for (int k = 3; k >= 0; k--) 
        cout << (n >> k & 1) ; // 核心代码
    
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

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

-x = (~x+1)

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

x = 1010001000

~x = 0101110111

-x = ~x+1 = 0101111000

x & -x = x & (~x+1) = 1000

#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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

离散化

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

关于unique():

  • 使用前需排序
  • 所有不重复的元素排在数组的最前面,数组末尾未占用的位置保留原来的值
  • 返回值是不重复的元素个数(标准说法是去重之后的尾地址),即重复元素的第一位,便于erase对其进行删除
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
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

区间和

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

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

开3*10^5的原因是总共数的个数,包括了n, 2m(l,r), 它们为10^5

区间和

#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;
}
  • 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

unique()去重算法源码剖析

本质:双指针

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

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
  • 4
  • 5
  • 6
  • 7
  • 8

区间合并

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

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

  1. 彼此互不相交
  2. 后一个区间被前一个区间包含
  3. 后一个区间与前一个有相交的部分
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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

参考资料

Acwing算法基础课

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/728732
推荐阅读
相关标签
  

闽ICP备14008679号