基础算法 - Mingchen's Blog

排序

快速排序

模板

#include <cstdio>
#include <iostream> 
#include <algorithm>

using namespace std;
const int N = 100010;
int q[N];
int n;

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)
    {
        while(q[++ i] < x);
        while(q[-- j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    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;
}

快速选择

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
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)
    {
        while (q[++ i] < x);
        while (q[-- j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    if (j - l + 1 >= k) return quick_sort(q, l, j, k);
    else return quick_sort(q, j + 1, r, k - (j - l + 1));
}

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

归并排序

模板

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int q[N], tmp[N];
int n;

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

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

逆序对的数量

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

#define ll long long

using namespace std;
const int N = 100010;
int n;
ll ans;
int q[N], tmp[N];

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]) tmp[k ++ ] = q[i ++ ];
        else
        {
            tmp[k ++ ] = q[j ++ ];
            ans += mid - i + 1;
        }
    }
    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);
    printf("%lld", ans);
    return 0;
}

二分

整数二分

数的范围

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int a[N];
int n, q, k;

int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    while (q -- )
    {
        scanf("%d", &k);
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (a[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if (a[l] != k) printf("-1 -1\n");
        else
        {
            printf("%d ", l);
            l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (a[mid] <= k) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", l);
        }
    }
    return 0;
}

实数二分

数的三次方根

#include <cstdio>

using namespace std;

double n;

int main()
{
    scanf("%lf", &n);
    double l = -100, r = 100;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid <= n) l = mid;
        else r = mid;
    }
    printf("%.6lf", l);
    return 0;
}

高精

高精度模板存数时都采用小端方式，整数的低位存在数组的低位（为了进位方便）

高精加

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
vector<int> A, B;

vector<int> add(vector<int> &A, vector<int> &B)
{
    int t = 0;
    vector<int> c;
    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;
    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');
    vector<int> C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    return 0;
}

高精减

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;
vector<int> 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(); i >= 0; i -- )
        if (A[i] != B[i]) return A[i] > B[i];
    return true;
}

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;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); //去除前导零
    return C;
}

int main()
{
    string 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))
    {
        vector<int> C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    }
    else
    {
        vector<int> C = sub(B, A);
        cout << '-';
        for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    }
    return 0;
}

高精乘

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> A;

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;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

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

高精除

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
vector<int> A;

vector<int> div(vector<int> &A, int b, int &t)
{
    vector<int> C;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        t = t * 10 + A[i];
        C.push_back(t / b);
        t %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

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

前缀和和差分

差分是前缀和的逆运算
前缀和是用来快速求出数组中一段连续区间的和（ $O(1)$ ）
差分是用来快速求出对数组中一段连续区间同时加上一个数后的数组结果（ $O(1)$ ）

一维前缀和

#include <cstdio>

using namespace std;

const int N = 100010;
int a[N], s[N];
int n, m;

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

二位前缀和

#include <cstdio>

using namespace std;

const int N = 1010;
int a[N][N], s[N][N];
int n, m, q, x1, y1, x2, y2;

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 ++ )
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    while (q -- )
    {
        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;
}

一维差分

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

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]);
    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);
    }
    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1], printf("%d ", b[i]);
    
    return 0;
}

二维差分

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;
int n, m, q;
int b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;		//表示在a数组中位于(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);
    int tmp = 0;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            scanf("%d", &tmp);
            insert(i, j, i, j, tmp);
        }
    }
    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);
    }
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            b[i][j] += b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1];
            printf("%d ", b[i][j]);
        }
        puts("");
    }
            
    return 0;
}

双指针

最长连续不重复子序列

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, a[N], s[N];
int res;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0, j = 0; i < n; i ++ )
    {
        s[a[i]] ++ ;
        while (j < i && s[a[i]] > 1) s[a[j ++ ]] -- ;
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}

位运算

求x的二进制表示中的第k位

x >> k & 1

求x的二进制表示中最后一位1出现的位置（lowbit）

例： $1001010100_2$ ，返回 $100_2$

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

二进制中1的个数

#include <cstdio>

using namespace std;

int n, tmp;

int cal(int t)
{
    int res = 0;
    while (t)
    {
        t -= (t & -t);
        res ++ ;
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &tmp);
        printf("%d ", cal(tmp));
    }
    return 0;
}

离散化

当有一个整数序列，这些整数的值域非常大 $(>10^9)$ ，但数字个数 $(n)$ 较少，即分布较为稀疏。现需要用到这些整数作为数组的下标，无法开一个超级大的数组，只能将这些整数离散化，按其原来的相对大小映射为一串连续的值 $(\leq n)$ 。

整体思路是：排序 $\rightarrow$ 去重 $\rightarrow$ 映射（一般映射为数组下标+1（二分查找））

区间和

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

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 f(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 l + 1;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});
        alls.push_back(x);
    }
    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(), alls.end());
    // unique()将数组非重复的元素排到前面，返回第一个重复元素的位置指针
    // erase()为删除操作
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    for (int i = 0; i < add.size(); i ++ )
    {
        a[f(add[i].first)] += add[i].second;
    }
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
    for (int i = 0; i < query.size(); i ++ )
    {
        printf("%d\n", s[f(query[i].second)] - s[f(query[i].first) - 1]);
    }
    return 0;
}

区间合并

模板

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;
vector<PII> a;
int res;

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) 
    {
        int l, r;
        cin >> l >> r;
        a.push_back({l, r});
    }
    sort(a.begin(), a.end());
    int p = -2e9, q = -2e9;
    for (int i = 0; i < n; i ++ )
    {
        if (q < a[i].first) p = a[i].first, q = a[i].second, res ++ ;
        else q = max(q, a[i].second);
    }
    cout << res << endl;
    return 0;
}

算法

#算法 #排序 #二分 #高精度 #前缀和与差分 #双指针 #位运算 #离散化 #区间合并 #c++

基础算法

https://lmc20020909.github.io/基础算法/

作者

Liu Mingchen

发布于

2023年4月16日

许可协议

CSAPP阅读札记——第二章上一篇

批判性思维复习下一篇