Krocz's Blog

望云登坡

0%

算法模板

发表于 更新于 分类于
本文字数： 6.2k 阅读时长 ≈ 11 分钟

1.快速排序

时间复杂度：$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
void quick_sort(int l, int r)
{
    if(l >= r) return;
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i++; while(a[i] < x);
        do j--; while(a[j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j), quick_sort(j + 1, r);
}

1.1 选择第K大的数字(quick_select)

时间复杂度：$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int quick_select(int l, int r, int k)
{
    if(l >= r) return a[l];
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i++; while(a[i] < x);
        do j--; while(a[j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    int cnt = j - l + 1;
    if(cnt >= k) return quick_sort(l, j, k);
    else return quick_sort(j + 1, r, k - cnt);
}

1.1.1 证明

快排的时间复杂度是$O(nlogn)$直观上还是好理解的，但是这个算法为什么不是$O(nlogn)$而是$O(n)$呢？

在平均情况下，第一次需要遍历$n$个数，第二次需要遍历$\frac{n}{2}$个数,…，即：

$$n + \frac{n}{2} + \frac{n}{4} + … = n(\frac{1}{2} + \frac{1}{4} + …) = n\sum_{i=0}^{log_2^n}\frac{1}{2^i} = 2n - 2 = O(n)$$

快速寻找相较快排每一次仅需要遍历一半的数量，所以复杂度降低了

2.归并排序

时间复杂度：$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
void merge_sort(int l, int r)
{
    if(l >= r) return;
    int mid = l + r >> 1, i = l, j = mid + 1, k = l;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    while(i <= mid && j <= r)
        if(a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];
    while(i <= mid) b[k++] = a[i++];
    while(j <= r)   b[k++] = a[j++];
    for(i = l; i <= r; i++)  a[i] = b[i];
}

2.1 求逆序对的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LL merge_sort(int l, int r)
{
    if(l >= r) return 0;
    int mid = l + r >> 1, i = l, j = mid + 1, k = l;
    LL cnt = merge_sort(l, mid) + merge_sort(mid + 1, r);
    while(i <= mid && j <= r)
        if(a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++], cnt += mid - i + 1;
    
    while(i <= mid) b[k++] = a[i++];
    while(j <= r) b[k++] = a[j++];
    
    for(i = l; i <= r; i++) a[i] = b[i];
    return cnt;
}

3. 二分

时间复杂度：$O(logn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while(l < r)
{
	int mid = l + r >> 1;
	if(a[mid] >= k)
		r = mid;
	else
		l = mid + 1;
}

while(l < r)
{
	int mid = l + r + 1 >> 1;
	if(a[mid] <= k)
		l = mid;
	else
		r = mid - 1;
}

除了模板还需要说明的是在算法退出循环时，下标l总是在刚好能够满足if语句中条件的位置上。例如序列：

1
1 2 4 4 4 5 6 9，k=4

如果条件为if(a[mid] >= k)，则l会指向第一个4所在位置；而当条件为if(a[mid] > k)时，则l会指向5所在的位置。

4.高精度

使用string将高精度数读入，然后将每一位依次放入vector<int>中。

4.1 高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> add(vector<int> a, vector<int> b) {
    vector<int> c(max(a.size(), b.size()) + 10, 0); 
    for (int i = 0; i < a.size(); i ++) c[i] += a[i];
    for (int i = 0; i < b.size(); i ++) c[i] += b[i];
    // 处理进位
    for (int i = 0; i + 1 < c.size(); i ++) {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    // 处理前导零
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    reverse(c.begin(), c.end());
    return c;
}

4.2 高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> mul(vector<int> a, vector<int> b)
{
    vector<int> c(a.size() + b.size() + 10, 0);
    for(int i = 0; i < a.size(); i ++)
        for(int j = 0; j < b.size(); j++)
            c[i + j] += a[i] * b[j];
     // 处理进位
    for(int i = 0; i < c.size(); i++)
    {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    // 处理前导零
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    reverse(c.begin(), c.end());
    return c;
}

4.3 高精度减法

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

vector<int> sub(vector<int> &a, vector<int> &b)
{
    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) % 10);
        if(t < 0) t = -1;
        else t = 0;
    }
    while(c.size() > 1 && !c.back()) c.pop_back();
    reverse(c.begin(), c.end());
    return c;
}


if(cmp(a , b))  c = sub(a , b);
else    cout << "-", c = sub(b , a);

4.4 高精度除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> div(vector<int> a, int b, int &r)
{
    vector<int> c;
    for(int i = 0; i < a.size(); i++)
    {
        r = r * 10 + a[i];
        c.push_back(r / b);
        r %= b;
    }
    // vector只能从末尾删除元素
    reverse(c.begin(), c.end());
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

5.前缀和 & 差分

5.1 前缀和

(1) 一维

1
2
3
4
5
6
7
for(int i = 1; i <= n; i++) 
{
    cin >> s[i];
    s[i] += s[i - 1];
}

cout << s[r] - s[l - 1] << endl;

(2) 二维

1
2
3
4
5
6
7
8
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
    {
        cin >> s[i][j];
        s[i][j] = s[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
    }

cout << s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1] << endl;

5.2 差分

(1) 一维

1
2
3
4
5
6
7
for(int i = 1; i <= n; i++)
{
    cin >> s[i];
    a[i] = s[i] - s[i-1];
}

a[l] += c;  a[r + 1] -= c;

(2) 二维

1
2
3
4
5
6
7
for(int i = 1; i <= n; i++)
	for(int j = 1; j <= m; j++)
	{
		cin >> s[i][j];
		a[i][j] = s[i][j] - s[i][j-1] - s[i-1][j] + s[i-1][j-1];
	}
a[x1][y1] += c; a[x2+1][y1] -= c;  a[x1][y2+1] -= c; a[x2+1][y2+1] += c;

6.离散化

应用场景：元素的位置下标范围非常大，但是元素分布很稀疏个数不多

主要思路：将所有出现的元素的位置下标收集在数组alls中。假设排序后去重数组alls有n个元素，就将其映射到新的下标0~n-1，从而仅使用n个空间来存储下标范围远大于n的数，具体做法是传入元素位置下标，通过二分查找该下标在数组alls中的位置，从而输出新的下标

6.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
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 300010;
#define x first
#define y second

int s[N];
typedef pair<int,int> PII;
vector<int> alls;
vector<PII> add, q;

int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(alls[mid] <= x)
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int main()
{
    int n, m, x, c, l, r;
    cin >> n >> m;
    // 收集使用到的所有元素的下标
    for(int i = 0; i < n; i++)
    {
        cin >> x >> c;
        alls.push_back(x);
        add.push_back(PII(x, c));
    }
    for(int i = 0; i < m; i++)
    {
        cin >> l >> r;
        alls.push_back(l);
        alls.push_back(r);
        q.push_back(PII(l, r));
    }
    // 排序 + 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    // 先求出原数组
    for(int i = 0; i < n; i++)
    {
        int idx = find(add[i].x);
        s[idx] += add[i].y;
    }
    // 然后求出前缀和数组
    for(int i = 1; i < alls.size(); i++)
        s[i] += s[i - 1];
    // 最后输出区间和
    for(int i = 0; i < m; i++)
    {
        int lidx = find(q[i].x), ridx = find(q[i].y);
        cout << s[ridx] - s[lidx - 1] << endl;
    }
    return 0;
}

在排序和去重的步骤中：

1
2
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

unique()将相邻的重复元素移动到数组末尾，然后迭代器指向第一个重复元素的下标，因此需要先排序，然后去重

7. 质数

一个合数可以质数分解，则必然被前面的某个质数划去

任何一个合数只会被其最小质因子筛掉：

  1. $i\ % \ p[j] == 0$

    $p[j]$ 一定是 $i$ 的最小质因子，$p[j]$ 一定是 $p[j] * i$ 的最小质因子

  2. $i \ % \ p[j] \ != 0$

    $p[j]$ 一定小于 $i$ 的所有质因子，$p[j]$ 也一定是 $p[j] * i$ 的最小质因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 线性筛法：O(n)
 * 每一个合数都会被它的最小质因子筛掉
 * if(i % primes[j] == 0)  break;  保证pj 是 i * pj的最小质因子
 */
void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i , minp[i] = i;
        for(int j = 0; primes[j] <= n / i; j++)
        {
            int t = primes[j] * i;
            st[t] = true;
            minp[t] = primes[j];
            if(i % primes[j] == 0)  break;
        }
    }
}