历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

笔记—基础算法

作者：

CodeSlogan , 2022-02-07 00:20:06 , 所有人可见 , 阅读 267

2

1

前言

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

排序

需注意边界问题

快速排序

确定分界点
调整区间，使x左边的区间都小于等于x（此时区间内不一定是有序的），右边则大于
递归处理左右两段

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.快速排序

归并排序

确定分界点为首末中点
以中点为界，递归排序中点两侧使其有序
归并，合二为一

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.归并排序

二分

整数

版本一

边界点归于左半边，从而将[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;
}

版本二

边界点归于右半边，从而将[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;
}

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

高精度

由于在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;
}

减法

主要的难点在于借位与进位

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

乘法

注意如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;
}

除法

余数需要同时传入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;
}

前缀和

前缀和指数列中前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;
}

差分

与前缀和互为逆运算

创建一数组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;
}

AcWing797.差分

双指针算法

常用问题分类：

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

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

// 朴素解法 时间复杂度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只增不减

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

最长不重复子序列

序列不一定递增

#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表示取出当前最后一位

#include <iostream>
using namespace std;

int main() {
    int n = 10;

    for (int k = 3; k >= 0; k--) 
        cout << (n >> k & 1) ; // 核心代码

    return 0;
}

一个数的二进制中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;
}

离散化

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

关于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
}

区间和

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

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

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

[HTML_REMOVED]

#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]

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

区间合并

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

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

彼此互不相交
后一个区间被前一个区间包含
后一个区间与前一个有相交的部分

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