知新_RL

这个屌丝很懒，什么也没留下！

热门标签

【算法】基础算法学习总结_逆序对博弈

作者：知新_RL | 2024-04-27 11:20:34

踩

逆序对博弈

一、基础算法

1.1 排序

快速排序

算法思想
quick_sort

【模板题】快速排序

在这里插入图片描述

// 快速排序模板

#include <iostream>

using namespace std;
const int N = 100000+10;

int b[N];

void quick_sort (int q[], int l, int r)
{
    if (l >= r) return;
    int i = l- 1, j = r + 1;
    int x = q[(l+r) /2 ];  // 取中间值的时候AC了:)

    while (i < j)
    {
        do i++; while (q[i] < x); // 不加=，一旦达到值x就停下来；否则遇到特殊情况可能停不下来
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort (q, l, j); // 用j不发生边界问题 只有2个数的情况死循环
    quick_sort (q, j+1, r);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n;i++) scanf("%d", &b[i]);

    quick_sort(b, 0, n-1);

    for (int i = 0; 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

第k个数

在这里插入图片描述
思路：只有参考点x的位置是确定的，参考点左侧的数和右侧的数位置不一定对。只有参考点x是可以返回的
参考代码：

long long quick_sort (long long q[], int l, int r, int k)
{
    if (l >= r) return q[l];

    int i = l -1, j = r + 1, x = l + r >> 1;
    long long xn = q[x];

    while (i < j)
    {
        do i++; while (q[i] < xn);
        do j--; while (q[j] > xn);
        if (i < j) swap(q[i], q[j]);
    }
    int cur;
    if (q[i] == xn)  // 确定参考点位置在i，还是j
        cur = i + 1;
    else cur = j + 1;
    if (cur == k) return xn;
    else if (cur > k) quick_sort(q, l, j, k);
    else quick_sort(q, j + 1, r, k);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

改进：永远保证第 k 小的数在 [l, r] 的区间上。递归的出口是区间上只有一个数，那么这个数就是第 SL 小的数。
在这里插入图片描述
程序代码

int quick_select(int q[], int l, int r, int k)
{
    if (l == r) return q[l];
    int i = l - 1, j = r + 1;
    int x = q[i + j >> 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;
    if (sl >= k) return quick_select(q, l, j, k);
    else return quick_select(q, j + 1, r, k - sl);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

归并排序

算法思想

// 归并排序

#include <iostream>

using namespace std;

int q[100000 + 10];
int n;
int tmp[100000+10];

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

    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];

    for (i = l, j = 0; j < k; 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;
}
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

思路：逆序对共有三种存在的可能，两个数全在左边，两个数全在右边，左右各有一个数。尽管有三种情况，但当我们递归左边和右边，直至左右边都只有一个数，前两种情况已经包含在了第三种情况中。所以 merge_sort(l, mid) 处理第一种情况， merge_sort(mid+1, r) 处理第二种情况。关键在于求第三种情况下的逆序对，这需要与归并过程结合。
在这里插入图片描述
归并逆序对：

参考代码：

typedef long long LL;

LL merge_sort(int l, int r)
{
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(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++];
            res += mid - i + 1;
        }
    }
    while(i <= mid ) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.2 二分

算法思想

【模板题】数的范围

在这里插入图片描述
模板代码

#include <iostream>
using namespace std;

int n, q;
int b[100000 + 10];

int main()
{

    scanf("%d", &n);
    scanf("%d", &q);

    for (int i = 0; i< n; i++) scanf ("%d", &b[i]);

    while (q--)
    {
        int x;
        int l = 0, r = n - 1;
        int mid;
        scanf ("%d", &x);
        // 模板1***********************************************
        while (l < r)
        {
            mid = l + r >> 1;
            if (b[mid] >= x) r = mid;
            else l = mid + 1;
        }
        // 模板1***********************************************
        if(b[l] != x) printf("-1 -1\n");
        else
        {
            printf("%d ", l);
            l = 0, r = n - 1;
            // 模板2***********************************************
            while (l < r)
            {
                mid = l + r + 1>> 1;
                if (b[mid] <= x) l = mid;
                else r = mid -1;
            }
            // 模板2***********************************************
            printf("%d\n", l);
        }
    }

    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

浮点数二分

不用考虑边界，设置好二分结束条件即可
代码模板：

int main()
{
    float x;
    scanf ("%f", &x);

    float l = -100, r = 100;
    float mid;
    while (r - l > 1e-6)
    {
        mid = (l + r) /2;
        if (mid * mid * mid > x) r = mid;
        else l = mid;
    }
    printf("%.2f\n", l);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.3 高精度

常用高精度问题分为四类：A+B, A-B, A*b, A/b。（大写表示高精度数，小写表示一般数用int表示）对于这四类情况，我们要解决的问题有两个：

存储高精度数
模拟四则运算

高精度存储

高精度数需要用数组存储，为了操作方便，这里用C++的 vector 存储。总结基本用法如下：

包含头文件#include <vector>
初始化 vector a(10)，定义10个 int 元素；vector a(10, 1)设置初值为1
a.back() // 返回最后一个元素
a.front()
a[i]
a.pop_back() // 删除最后一个元素
a.push_back(x) // 在数组最后插入x
a.size() // 返回a中元素个数
和字符数组同样的访问方式s[i], cin, cout
a.begin()返回头指针，指向第一个元素
a.end()返回尾指针，指向最后一个元素的下一个单元
reverse(a.begin(), a.end())将vector前后逆序

另外，以字符串形式读入高精度数，使用string类：

包含头文件#include <string>
s.size() // 获取string长度，string末尾没有’\0’，返回的是真实长度
s1 + s2 拼接字符串
为了进位方便，高精度数据从低位开始存储，即，12345 按照 5 4 3 2 1 的顺序存进 vector。

加法

加法的进位只有 0 和 1
vector输出时从高位到低位，注意循环的方向
模板

vector<int> add (vector<int> &A, vector<int> &B)
{
	if (A.size() < B.size()) return add (B, A);
	vector<int> C;
	int t = 0;
	for (int i = 0; i < A.size() || t != 0; i++)
	{
		if (i < A.size()) t += A[i];
		if (i < B.size()) t += B[i];
		C.push_back(t % 10);  // 求出Ci
		t /= 10;  // 求出ti，取值为0或1
	}
	return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

string要用cin读入，用scanf(“%s”, s);会报错
auto C = add(A, B);编译器会自动推断C的类型

减法

一定注意遍历vector时的起始位置和遍历方向
加减法都要解决两个问题：计算当前位结果Ci，处理进位/借位ti
模板

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);  // 求Ci
        if (t < 0) t = 1;  // 求ti
        else t = 0;
    }
	
	// C.size() - 1 可以写成 C.back()
    while (C.size() > 1 && C[C.size() - 1] == 0) C.pop_back();  // 去除前导0
    return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

高精度x低精度

C = A * b把 b 看成一个整理进行乘法运算，尽管 b 可能不止 1 位
t = Ai * b + ti，Ci = t % 10，ti = t / 10
模板

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    // Ci和ti的更新方式，和加法是一样的
    for (int i = 0, t = 0; i < A.size() || t > 0; 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();  // 当 b==0 时去除前导0

    return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

高精度 / 低精度

C = A / b … r
r = r * 10 + A[i], Ci = r / b, r = r % b
除法运算不同于加、减、乘的运算顺序，是从高位向低位运算
使用reverse函数需要包含头文件#include <algorithm>
模板

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 = r % b;
    }

    reverse (C.begin(), C.end());  // 恢复高精度数的存储顺序
    while (C.size() > 1 && C.back() == 0) C.pop_back();  // 去除前导0
    return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.4 前缀和及差分

一维前缀和

根据已知数组a[1], a[2], …, a[n]构造数组S[0], S[1], …, S[n]，S[n]表示前n项数组元素的和。注意a数组从 1 开始，S数组从 0 开始

前缀和的用处是求数组中任意区间内数组元素的和，例如求[l, r]区间和，res = S[r] - S[l - 1]
模板

    scanf ("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    s[0] = 0;
    for (int i = 1; i <= n; i++)  // 因为a数组从 1 开始，所以 i 要取到 n 
        s[i] = s[i - 1] + a[i];  // 生成前缀和数组s[N]

    while (m--)
    {
        int l, r;
        scanf ("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);  // 前缀和应用公式
    }
1
2
3
4
5
6
7
8
9
10
11
12

二维前缀和

为二维数组a[i, j]构造前缀和数据s[i, j]，前缀和数组表示[i, j]左上角所有元素的和

二维前缀和的作用：求二维区域内，左上角点[x1, y1]到右下角点[x2, y2]围成的矩形区域中所有元素的和。
应用前缀和时需要注意边界线上的元素是否取到，是否重复加、重复减：res = s[x2, y2] - s[x2, y1 - 1] - s[x1 - 1, y2] + s[x1 - 1, y1 - 1]
构建前缀和的过程：s[i, j] = s[i - 1, j] + s[i, j - 1] -s[i - 1, j - 1] + a[i, j]
模板

#include <iostream>

const int N = 1010;
int n, m, q;
long a[N][N], s[N][N];

int main()
{
    scanf ("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%ld", &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--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%ld\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
    	// 使用前缀和数组，O(1)
    }
    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

差分

构造数组b[1], b[2], …, b[n]使得b[n]数组是a[n]的前缀和，即a[n] = b[1] + b[2] + … + b[n]

差分数组的作用：给区间[l, r]上的元素都加上固定值c:b[l] += c, b[r + 1] -= c，再对 b 数组求前缀和得到 a 数组
差分数组的构造：初始假设 a 数组全0，那么 b 数组也全0。将 a 数组的元素值依次插入 b 数组中去，元素插入长度为 1。这样可以通过 1 中的方法构造差分数组
模板

// 在[l, r]区间上插入固定值c
void _insert (int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

// 代码片段
for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);

for (int i = 1; i <= n; i++) _insert(i, i, a[i]);  // 初始化b[]

while (m --)
{
	int l, r, c;
    scanf ("%d%d%d", &l, &r, &c);
    _insert(l, r, c);  // m次插入固定值

}
for (int i = 1; i <= n; i++) b[i] += b[i - 1];  // 对b[]求前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二维差分

二维情况下数组下标有 x 和 y 两个维度。给b[i, j]加上一个数值相当于对(i, j)坐标右下角所有元素加上固定值

给(x1, y1), (x2, y2)的区域加上固定值c，关键是考虑区域边界上的值：
- b[x1, y1] += c
- b[x2 + 1, y1] -= c
- b[x1, y2 + 1] -= c
- b[x2 + 1, y2 + 1] += c
b 数组初始化的过程也采用insert差分函数插入
模板

// 进行差分操作的insert函数
void _insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

// 输入输出处理
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++)
        _insert(i, j, i, j, a[i][j]);

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 - 1][j] + b[i][j - 1] - b[i - 1][j - 1];  // 求二维前缀和

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

1.5 双指针算法

实质：双指针算法实质上是优化 i，j 两重循环，根据 i，j 之间的性质把 O(n*2) 的复杂度优化到 O(n)
应用思路：先想一个朴素的做法，然后思考 i，j 之间的关系，优化算法
代码模板：

for (i = 0, j = 0; i < n; i++)
{
	while(j < i && check(i, j)) j++;
	

	// 每道题目的具体逻辑
}
1
2
3
4
5
6
7

题目：最长连续不重复子序列
在这里插入图片描述
每次 i 迭代得到一个最长子序列，长度为 i - j + 1，最后取其中最大的情况
参考代码：

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

int main()
{
    scanf ("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);

    int max_s = 0;
    for(int i = 0, j = 0; i < n; i++)
    {
        s[q[i]]++;
        while(s[q[i]] > 1)
        {
            s[q[j]] --;
            j++;
        }
        max_s = max(max_s, i - j + 1);
    }

    printf("%d\n", max_s);
    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

数组元素的目标和：
在这里插入图片描述
双指针优化：对于 a 数组中每一个 i，从 b 数组中找出最小的 j 使得 a[i] + b[j] > x。当 i 向后移动时，j 不会后退，只能减小。
当前版本代码：

int main()
{
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    for (int i= 0; i < m; i++) scanf("%lld", &b[i]);

    int i, j = m - 1, flat = 0;
    for (i = 0; i < n; i++)
    {
        flat = 0;
        while (j >= 0 && a[i] + b[j] > x) {j--; flat = 1;}
        if (a[i] + b[j] == x) break;
        if (flat == 1)
            j ++;
    }
    cout << i << " " << j << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.6 位运算

共有两个常用操作

看二进制数第 k 位是几

(n >> k) & 1
1

lowbit(x)返回 x 的最后一位 1。例如，x = 1010, lowbit(x) = 10

x & -x
1

-x 的在计算机中补码表示为 (~x + 1)，当x = 1010 … 1000 … 时，~x = 0101 … 0111 … ，~x + 1 = 0101 … 1000 …
题目：二进制中1的个数

#include <iostream>
using namespace std;

typedef long long LL;

LL lowbit(int n)
{
    return n & -n;
}

int main()
{
    LL n, re;
    int counts = 0;
    scanf("%lld", &n);
    while ((re = lowbit(n)) > 0)
    {
        counts++;
        n -= re;
    }
    printf("%d\n", counts);
    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

1.7 离散化

题目：区间和
在这里插入图片描述

在这里插入图片描述
关于pair

定义：typedef pair<int, int> PII
头文件：#include <utility>
给vector<PII>赋值：push_back({a, b})
给vector<PII>排序：sort默认先以first排，再以second排
vector<PII>的遍历：for (auto item:query)，如果要修改 vector 的值，就在遍历时使用引用，for (auto &item:query)
访问PII a：a.first, b.first

题解：

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
const int N = 30010;
typedef pair<int, int> PII;
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 l + 1;
}

int main()
{
    scanf("%d%d", &n, &m);

    // 读入插入点
    for (int i = 0; i < n; i++)
    {
        int x, c;
        cin >> x >> c;
        alls.push_back(x);
        add.push_back({x, c});
    }

    // 读入查询点
    for (int i = 0; i < m; i++)
    {
        int l, r;
        cin >>l >> r;
        alls.push_back(l);
        alls.push_back(r);
        query.push_back({l, r});
    }

    // 离散化数组去重，alls的下标就是离散化的位置，alls.size就是离散化矩阵的长度，
    // a[N]维护的序列实际是alls，alls里面存的是离散化前的数，alls下标是离散化的数，a[N]通过相同的下标和alls关联起来，存放具体的值
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    for (auto item : add)
    {
        int x = _find(item.first);
        a[x] += item.second;
    }

    for (int i = 1; i <= alls.size(); i++)
        s[i] = s[i - 1] + a[i];

    // 处理查询
    for (auto item : query)
    {
        int l = _find(item.first);
        int r = _find(item.second);
        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
68
69
70
71
72

模板

vector<int> alls;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// 排序去重之后的alls数组就是离散化数组

// 二分求出x对应的离散化的值
// 找出第一个大于等于x的位置
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 l + 1;  // 映射到1, 2, ..., n 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.8 区间合并

算法思想：

先按照左端点给各区间排序
遍历区间，后一个区间与当前区间只存在三种情况
情况一：当前 st，ed保持不变，继续遍历
情况二：更新ed，继续遍历
情况三：把当前区间存储为独立区间，更新st，ed
在实际算法中可以把情况一和情况二写在一起

题目：区间合并
在这里插入图片描述

一点启发：设置变量记录当前位置，例如这里的st和ed，主要还是为了处理边界情况，同时写法也更显得简便。

二、数据结构

2.1 数组模拟链表

n[N]：存放节点的值
ne[N]：存放下一个节点的标号，通过相同的idx下标将节点的内容联系起来
idx：可分配的节点空间下标
head：头指针，指向头节点，-1表示链表为空

初始化

void init()
{
    head = -1;
    idx = 0;
}
1
2
3
4
5

插入

// 插到头节点
void insert1(int x)
{
    n[idx] = x;
    ne[idx] = head;
    head = idx++;  // 头指针指向idx
}

// 插到第 i+1 次插入的数后面
void insert2(int i, int x)
{
    n[idx] = x;
    ne[idx] = ne[i];
    ne[i] = idx;
    idx++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

删除

// 删除 i 后面的节点，i是插入的顺序，即可用的存储单元idx
// 在题目条件中 k = idx + 1
void remove_(int i)
{
    ne[i] = ne[ne[i]];
}
1
2
3
4
5
6

2.2 双向链表

idx = 0作为头指针，idx = 1作为尾指针，头尾指针不存储数据
e[N]：存储节点数值
l[N]：左边节点下标
r[N]：右边节点下标
idx：当前可用下标
初始化

// 给首尾分配节点，但没有数据
// idx从2开始，k从1开始
void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}
1
2
3
4
5
6
7
8

表头插入

void insert1(int x)
{
    e[idx] = x;
    r[idx] = r[0];
    l[r[idx]] = idx;
    l[idx] = 0;
    r[0] = idx++;
}
1
2
3
4
5
6
7
8

表尾插入

void insert2(int x)
{
    e[idx] = x;
    r[l[1]] = idx;
    l[idx] = l[1];
    r[idx] = 1;
    l[1] = idx++;
}
1
2
3
4
5
6
7
8

删除节点

// 删除 k 节点
void remove1(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
1
2
3
4
5
6

k右边插入，左边插入调用当前函数实现

// 在 k 右边插入
void insert3(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[r[k]] = idx;
    l[idx] = k;
    r[k] = idx++;
}
1
2
3
4
5
6
7
8
9

注意：因为保留首尾节点 idx 从 2 开始使用，第 k 次插入的数对应的 idx 应该是 k+1，函数中的 k 是 idx

2.3 栈

stk[N]：存储栈元素
tt：标记栈顶，初始化为0

初始化

 // init
 tt = 0;
1
2

入栈

 // push
 stk[++tt] = x;
1
2

出栈

tt--
1

判断栈空

if (tt < 1)
	printf("栈空\n");
1
2

2.4 队列

hd, tl：头指针和尾指针
que[N]：队列元素

初始化

void init()
{
    hd = tl = 0;
}
1
2
3
4

插入

void push(int x)
{
    que[tl++] = x;
}
1
2
3
4

弹出

void pop()
{
    hd++;
}
1
2
3
4

判断对列空

bool ety()
{
    if (hd == tl)
        return true;
    else return false;
}
1
2
3
4
5
6

2.5 单调栈

应用场景：求序列中每个数左/右边最近的比它大/小的元素
思想：当求左边最近的小元素时，如果一个靠右的元素有更小的值，那么左边的元素就不可能作为后面元素的最近值输出。单调栈是单调递增的
模板

for (int i = 1; i <= n; i++)  // 下标从1开始，具体实现的时候比较随意
{
	while (tt && check(stk[tt], i)) tt--;
	
	// 具体题目逻辑
	
	stk[++tt] = i;
}
1
2
3
4
5
6
7
8

2.6 单调队列

应用场景：滑动窗口中的最大值或最小值
思想：求最小值时，如果当前元素比对尾元素小，由于当前元素还比对尾元素“活得久”，那么对尾元素就不再被需要。单调队列是递增的
代码模板：

// 求窗口最小值
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh++;  // 移除队列中超出窗口的部分，从对头移出
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;  // 从队尾开始检查，比当前元素小的值被移出
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d ", a[q[hh]]);
    }
1
2
3
4
5
6
7
8
9

2.7 KMP

代码模板：

    scanf("%s%s", s1+1, s2+1);  // 从1开始存放匹配串
    int n = strlen(s1+1);
    int m = strlen(s2+1);

    // 求next数组
    for (int i = 2, j = 0; i <= m; i++)
    {
        while(j && s2[i] != s2[j + 1]) j = ne[j];  // 比较j+1的字符，包括j之前的字符是匹配的
        if (s2[i] == s2[j + 1]) j++;
        ne[i] = j;
    }

    // 匹配
    for (int i = 1, j = 0; i <= n; i++)  // 隐含当匹配串回溯到头，i++后重头匹配
    {
        while(j && s1[i] != s2[j + 1]) j = ne[j];
        if (s1[i] == s2[j + 1]) j++;
        
        // 匹配成功
        if (j == m)
        {
            printf("%d\n", i - m + 1);
            j = ne[j];
        }
    }

    for (int i = 1; i <= m; i++)
        printf("%d ", ne[i]);
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

2.8 Trie树

应用场景：存储字符串的集合，并快速查找字符串出现次数
算法思路：以树的形式存储字符串，儿子结点的数量是有限的
参考代码：

const int N = 100010;
char s[N];
int son[N][26];  // 存放每个结点的儿子结点，26个英文字母
int idx;  // idx = 0 表示根
int cnt[N];  // 标记终点坐标

void ins(char str[])
{
    int p = 0;  // 根节点
    for (int i = 0; str[i] != 0; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;  // son结点没有被标记时
        p = son[p][u];  // p就是idx，结点的下标
    }
    cnt[p]++;
}

int query(char str[])
{
    int p = 0;
    for (int i= 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
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

2.9 并查集

应用场景：询问两个元素是否在同一个集合；将两个集合合并
数据结构&算法思想：树型结构存储一个集合中的元素；p[x]维护每个结点的父节点
特点：集合元素是题目给定的1~n，无须用户输入
优化：路径压缩，查找的过程中将集合中的所有结点的父节点都指向根节点
变型：
1. size[N]维护集合结点总数
代码模板：

const int N = 100010;
int n, m;
int p[N];

int findd(int x)
{
    // 未到根节点
    if (p[x] != x) p[x] = findd(p[x]);  // 查找的同时完成了优化
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        p[i] = i;

    char op[10];
    int a, b;
    while (m --)
    {
        scanf("%s%d%d", op, &a, &b);
        if (!strcmp(op, "M"))
        {
            if (findd(a) != findd(b))
                p[p[a]] = p[b];
        }
        else
        {
            if (findd(a) == findd(b))
                printf("Yes\n");
            else
                printf("No\n");
        }
    }

    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

2.10 堆

应用场景：维护一个堆（小根堆/大根堆），可以实现如下操作----
1. 插入一个数
2. 求集合体最小值
3. 删除最小值
4. 删除任意元素
5. 修改任意元素
数据结构&算法思想：用完全二叉树heap[x]维护堆，实现两种基本操作void up(int x), void down(int x)
程序代码：

const int N = 100010;
int n, m;
int heap[N];
int sizee;  // 堆中结点数量

void down(int x)
{
    int t = x;  // 存放局部堆的三个元素中最小元素的结点下标
    if (x * 2 <= sizee && heap[x * 2] < heap[t]) t = x * 2;
    if (x * 2 + 1 <= sizee && heap[x * 2 + 1] < heap[t]) t = x * 2 + 1;
    if (t != x)
    {
        swap(heap[x], heap[t]);
        down(t);
    }

}

void up(int u)
{
    // 只须比较u和u/2的值
    while (u / 2 && heap[u / 2] > heap[u])
    {
        swap(heap[u / 2], heap[u]);
        u = u / 2;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)  // 从1开始存放，方便完全二叉树计算
        scanf("%d", &heap[i]);
    sizee = n;
    for (int i = n / 2; i >= 1; i--)
        down(i);  // 建堆
    while (m--)
    {
        printf("%d ", heap[1]);
        
        // 删除堆顶元素
        heap[1] = heap[sizee--];
        down(1);
    }

    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

变型：维护了插入索引ph和hp的堆

int heap[N];
int ph[N], hp[N];  // hp是用于辅助ph做交换的
int sizee;  // 堆中结点数量

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(heap[a], heap[b]);
}

void down(int x)
{
    int t = x;  // 存放局部堆的三个元素中最小元素的结点下标
    if (x * 2 <= sizee && heap[x * 2] < heap[t]) t = x * 2;
    if (x * 2 + 1 <= sizee && heap[x * 2 + 1] < heap[t]) t = x * 2 + 1;
    if (t != x)
    {
        heap_swap(x, t);
        down(t);
    }

}

void up(int u)
{
    // 只须比较u和u/2的值
    while (u / 2 && heap[u / 2] > heap[u])
    {
        heap_swap(u / 2, u);
        u = u / 2;
    }
}

int main()
{
    scanf("%d", &m);
    char op[10];
    int idx;  // idx是插入的序号

    while (m--)
    {
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            int x;
            scanf("%d", &x);
            idx++, sizee++;
            ph[idx] = sizee, hp[sizee] = idx;
            heap[sizee] = x;
            up(sizee);
        }
        else if (!strcmp(op, "PM"))
        {
            printf("%d\n", heap[1]);
        }
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, sizee);  // heap值交换后hp和ph也得跟着换
            sizee--;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            int k;
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, sizee);
            sizee--;
            down(k), up(k);
        }
        else
        {
            int k, x;
            scanf("%d%d", &k, &x);
            k = ph[k];
            printf("trans-k:%d\n", k);
            heap[k] = x;
            down(k), up(k);
        }

    }

    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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

2.11 整数哈希表

哈希表是将一个大空间映射到小空间的数据结构，需要解决两个问题。哈希函数h(x)和映射冲突
哈希函数h(x)通过取模运算x mod N(小空间规模)得到。N应取质数，且距离2的整数次幂尽可能远。这样的取法被证明是冲突可能最小的

// 求质数
    for (int i = 100000;;i++)
    {
        bool flag = true;
        for (int j = 2; j * j <= i; j++)
        {
            if (i % j == 0)
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            cout << i << endl;
            break;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

操作：添加和查找

（1）拉链法

数据结构：
- h[N]: 映射到的空间，h[N]的值是链表的头节点
- e[N]: 每个槽拉出的链表的元素值都放在e[N]中，逻辑上e[N]中存储了多条链表，物理上都是存储在一个数组结构中的
- ne[N]: 存放下一个结点位置，链表的一部分
题目：acwing 840
添加操作：

void insert_(int x)
{
    int k = ((x % N) + N) %N;  // 防止负数出现
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}
1
2
3
4
5
6
7

查找操作：

bool find_(int x)
{
    int k = ((x % N) + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
    {
        if (e[i] == x)
            return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10

（2）开放寻址法

核心功能：find(x)函数，如果x在哈希表中返回x的位置，如果x没在哈希表中返回x应该存在的位置

int find_(int x)
{
    int k = ((x % N) + N) % N;
    while (h[k] != null && h[k] != x)
    {
        k++;
        if (k > N)
            k = 0;
    }
    return k;
}
1
2
3
4
5
6
7
8
9
10
11

设置不在数据范围内的null，代表槽点为空值，其中memset使用16进制赋初值，所以null值被规定为16进制数

null = 0x3f3f3f3f;
// memset按字节赋值，int型占四个字节
memset(h, 0x3f, sizeof(h));
1
2
3

为了减小冲突，槽点大小一般要开成数据量的2~3倍

2.12 字符串哈希

应用场景：快速判断两个字符串是否相等
做法：将字符串的前缀映射到哈希值。将长度为k的前缀看作是k位P进制的数，这个数就是字符串前缀对应的哈希值。这里有三个经验结论，（1）字符串哈希不考虑冲突。（2）P取131或者13331并且mod 2^64时，冲突发生概率小。这里用unsigned long long定义前缀哈希数组，溢出时自动取模。（3）任何字符的哈希值不能为0，否则当出现“x”和“xx”时，哈希值会重复
与整数哈希的实现区别：不需要定义数组来表示哈希表，因为不需要处理冲突。哈希表隐含在数值中
应用：求[L, R]之间子串的哈希值，h[R] - h[L - 1] * P^(R - L + 1)
数据结构：unsigned long long h[N]存放字符串的前缀哈希值，p[N]存放P进制数的权值

// 数据结构
typedef unsigned long long ULL;
const int N = 100010;
ULL h[N], p[N];
int n, m;
int P = 131;

// 计算哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

// 处理字符串前缀哈希映射
p[0] = 1;
h[0] = 0;
for (int i = 1; i < n; i++)
{
    p[i] = p[i - 1] * P;
    h[i] = h[i - 1] * P + s[i];  // 哈希映射
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.13 STL

string:
- empty()
- size() / length()
- clear()
- s.sub_str(1, 2) // 返回子串，从下标1开始，返回2个字符
- printf(“%s\n”, s.c_str());

vector，定义变长的数组：

#include <vector>

// 初始化
vector<int> s(10);
vector<int> s(10, 1);

// 数组操作
s[0] = 1;
s[1] = 2;

// 插入、弹出数组尾
s.push_back(10);
s.pop_back();

// 数组长度
s.size();
s.empty();

// 数组清空
s.clear();

// 取首尾元素
cout << s.front() << endl;
cout << s.back() << endl;

// 取首尾指针，使用迭代器
s.begin();
s.end();
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

pair, 定义元素对:

// 定义及使用
pair<int, int> p;
p.first = 10;
p.second = 20;
cout << p.first << " " << p.second << endl;
1
2
3
4
5

queue:
- size()
- empty()
- front() 取队头
- back() 取队尾
- pop() 从队头弹出
- push() 从队尾插入
```
#include <queue>

// 清空queue
queue<int> q;
q = queue<int>();
1
2
3
4
5
```

priority_queue，有限队列，堆且默认是大根堆

push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素

#include <queue>

// 定义小根堆
// 方法1：黑科技
priority_queue<int> heap;
push(-x);

// 方法2：直接定义
priority_queue<int, vector<int>, greater<int>> heap;
1
2
3
4
5
6
7
8
9

stack，栈
- push()
- pop()
- top()
- empty()
- size()
deque，双端队列，效率低
set, multiset, map, multimap
```
#incldue <set>
#include <map>
1
2
```

unordered_set, unordered_multiset, unordered_map, unordered_multimap

#incldue <unordered_set>
#include <unordered_map>

/*
不支持lower_bound(x), upper_bound(x)
但增删改查时间复杂度是o(1)
unordered_map是哈希表
*/ 
1
2
3
4
5
6
7
8

bitset，压位，一个bit存储一个bool数（二进制）

#include <bitset>

bitset <10000> b;
// 支持逻辑运算，移位操作和[]
// any(), count(), none()
// set() 所有位置成1
// set(k, v) 第k位变成v
1
2
3
4
5
6
7

2.14 素数筛选

4. // 线性素数筛选 prime[0]存的是素数的个数
5. const int maxn = 1000000 + 5;
6. int prime[maxn];
7. void getPrime() {
8. 		memset(prime, 0, sizeof(prime));
9. 		for (int i = 2; i <= maxn; i++) {
10. 		if (!prime[i]) prime[++prime[0]] = i;
11. 		for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {
12. 			prime[prime[j] * i] = 1;
13. 			if (i % prime[j] == 0) break;
14. 		}
15. 	}
16. }
1
2
3
4
5
6
7
8
9
10
11
12
13

三搜索

3.1 DFS

思路：递归实现，搜索所有情况。搜索的顺序决定了代码的写法
典型例题：n-皇后，数字全排列
代码写法：设置递归出口，DFS回溯的时候恢复现场。注意让程序遍历所有可能情况（用循环或者递归实现）

3.2 BFS

数据结构：队列
典型例题：走迷宫，八数码
性质：在边权为1的图中，求最短路

int bfs(int x, int y)
{
	queue.push({x, y});
	while(queue非空){
		扩展所有可能结点
		满足条件的点queue.push
	}
	return 最短距离
}
1
2
3
4
5
6
7
8
9

3.3 图的存储

数据结构：邻接表，把无向图看成特殊有向图

int e[N], ne[N], head[N], idx;
// e和ne的下标是idx指针，head的下标是结点
void init()
{
	memset(head, -1, sizeof(head));
}
void add_line(int a, int b)
{
	e[idx] = b;
	ne[idx] = head[a];
	head[a] = idx++;
}
1
2
3
4
5
6
7
8
9
10
11
12

图的深度优先遍历

int e[N], ne[N], head[N], idx;
int st[N];

int dfs(int node)
{
	st[node] = 1;
	for (int i = head[node]; i != -1; i = ne[i]){
		int j = e[i];
		if (!st[j]){
			dfs(j);
		}
	}
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

图的广度优先遍历，求最短路

int head[N], e[N], ne[N], idx;
int d[N], que[N];
int tt = 0, hh = 0;
memset(head, -1, sizeof(-1));
memset(d, -1, sizeof(-1));

void bfs()
{
	que[tt++] = 1; //从node1开始搜索，求从node1到其他点的距离
	d[1] = 0;
	while (hh != tt){
		int now = que[hh++];
		for (int i = head[now]; i != -1; i = ne[i]){
			int j = e[i];
			if (d[j] == -1){
				d[j] = d[now] + 1;
				que[tt++] = j;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

图的拓扑排序

bool topsort()
{
	for(所有结点){
		que.push(入度为0的结点);
	}

	while (队列非空){
		now = 队头元素;
		for(now的所有边){
			结点入度--;
			if (结点度数为0)
				que.push(该结点);
		}
	}
	return 队尾指针 == n - 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.4 最短路算法

3.4.1 朴素Dijkstra

应用场景：单源最短路，边权值全为正数，稠密图
图存储数据结构：邻接矩阵
时间复杂度：O(n^2)

int g[N][N], dist[N];
bool st[N];
memset(g, 0x3f, sizeof(g));

int dijkstra()
{
	memset(dist, 0x3f, sizeof(dist));
	dist[1] = 0;
	for (迭代n次) // 每次确定一个结点的最短路
	{
		int t = -1; // 当前最短的路径点
		for (遍历n个结点) 
			找到dist最小的结点;
		st[t] = true;
		for ()
			用dist[t]更新n个结点;
	}
	if (dist[N] == 0x3f3f3f3f) return -1;
	else return dist[N];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.4.2 堆优化Dijkstra

应用场景：单源最短路，边权值全为正数，稀疏图
小根堆定义：priority_queue< PII, vector<PII>, greater<PII> > heap
时间复杂度：O(mlogn)
算法：

int g[N][N], dist[N];
bool st[N];
memset(g, 0x3f, sizeof(g));

int dijkstra()
{
	memset(dist, 0x3f, sizeof(dist));
	dist[1] = 0;
	priority_queue <PII, vector<PII>, greater<PII>> heap; //按照第一个关键字排序
	heap.push({0, 1});
	while (heap.size()) // 队列非空
	{
		auto t = heap.top();
		heap.pop();
		int var = t.second, distance = t.first;
		if (st[var]) continue;
		st[var] = true;
		
		for (邻接边)
			if (当前路径比dist段){
				用当前路径更新dist;
				heap.push({}); //heap中是{距离，结点};
			}
	}
	if (dist[N] == 0x3f3f3f3f) return -1;
	else return dist[N];
}
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

3.4.3 bellman_ford算法

应用场景：单源最短路，有负权边
图存储：使用结构体存储边
时间复杂度：O(nm)
算法：

struct Edge{
	int a, b, w;
}edge[M];

int bellman_ford()
{
	初始化dist;
	dist[1] = 0;
	for (遍历k次) //每一次到达的路径长度+1，限制的走过的边数不超过k
	{
		使用backup备份dist，使用backup更新最短路;
		for (遍历所有边)
		{
			dist[j] = min(dist[j], backup[a] + w); //更新最短路
		}
	}
	if (dist[n] > 0x3f3f3f3f / 2) return -1; //负权边可能会更新无穷大
	else return dist[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.4.4 spfa算法

思路：优化的bellman_ford算法
图的存储：邻接表
时间复杂度：O(m)，最坏O(nm)

int spfa()
{
	初始化dist;
	queue<int> q;
	q.push(1); //维护最短路有更新的结点
	st[1] = true;
	
	while (q.size())
	{
		int t = q.front();
		q.pop();
		st[t] = false;
		
		for (int i = head[t]; i != -1; i = ne[i])
		{
			j = e[i];
			如果存在更短的路径，更新dist[j];
			如果j不在队列中，把j加入队列;
		}
	}
	if (dist[n] > 0x3f3f3f3f  / 2) return -1;
	else return dist[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

引申应用：判断负环

int cnt[N];

int spfa()
{
	queue<int> q;
	所有结点push进队列;
	
	while (q.size())
	{
		int t = q.front();
		q.pop();
		st[t] = false;
		
		for (int i = head[t]; i != -1; i = ne[i])
		{
			j = e[i];
			如果存在更短的路径，更新dist[j]，更新cnt[j];
			如果cnt[j] >= n，返回true，找到负环;
			如果j不在队列中，把j加入队列;
		}
	}
	返回false，没有负环;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.4.5 floyd算法

图的存储结构：邻接矩阵
应用场景：多源汇最短路
算法：

void floyd()
{
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
1
2
3
4
5
6
7

3.5 最小生成树

3.5.1 Prim算法

对应：无向图，稠密图的最小生成树
数据结构：邻接矩阵

//思路
prim()
{
	dist[i] <- INF;
	for (循环n次) //每次把一个点加入生成树集合
	{
		t <- 集合外距离集合最近的点;
		for (1:n) 用t更新其他点到结合的距离;
		st[t] = true;
	}
}

// 模板
int prim()
{
    memset(dist, 0x3f, sizeof(dist));

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];

        for (int j = 1; j <= n; j++)
        {
            dist[j] = min(dist[j], g[t][j]);
        }
        st[t] = true;
    }

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

3.5.2 Kruskal算法

数据结构：结构体存储
应用场景：稀疏图
题目：Acwing859

//思路
kruskal()
{
	将所有边从小到大排序;
	for (1:m枚举所有边)
	{
		if (a和b不连通) //并查集
			把这条边加入集合中;
	}
}

//模板
typedef struct Edge
{
    int a, b, w;
} Edge;

bool cmp(Edge a, Edge b)
{
    if (a.w < b.w) return true;
    return false;
}

Edge edges[M];
int p[M];
int n, m;


int findd(int x)
{
    if (p[x] != x) p[x] = findd(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m, cmp);
    int res = 0, cnt = 0;

    for (int i = 1; i <= m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if (findd(a) != findd(b))
        {
            res += w;
            cnt ++;
            p[b] = a;
        }
    }

    if (cnt < n - 1) return -1;
    return res;
}
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

3.6 二分图

3.6.1 染色法

图存储：邻接表
二分图：把整个图的结点分成两类，结点内部无边，边全在结点之间
题目：Acwing860

//思路
t = true;
for (1:n遍历结点)
{
	if (i未被染色)
	{
		if(!dfs(i, 1)) //给i染上颜色1
		{
			t = false;
			break;
		}
	}
}

dfs(i, c)
{
	给i染上c;
	for (遍历i的邻接边)
	{
		if (j未染色) dfs(j, 3 - c);
		else
		{
			if (邻接点颜色 == 当前结点颜色) return false;
		}
	}
	reutrn true;
}

//模板
bool dfs(int i, int c)
{
    color[i] = c;

    for (int k = head[i]; k != -1; k = ne[k])
    {
        int j = e[k];
        if (!color[j])
        {
            if (!dfs(j, 3 - c)) return false;
        }
        else
        {
            if (color[j] == c) return false;
        }
    }

    return true;
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    bool t = true;
    for (int i = 1; i <= n; i++)
    {
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                t = false;
                break;
            }
        }
    }

    if (t) puts("Yes");
    else puts("No");

    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
68
69
70
71
72
73
74
75
76
77
78
79

3.6.2 匈牙利算法

应用场景：二分图下的图匹配问题
题目：acwing861
算法思路：

对每个左半部结点进行一次搜索
bool _find(int x)
{
	for (遍历x的所有连接点)
	{
		连接点为j;
		if (j未被访问)
		{
			if (j尚未匹配或者j原本匹配的点有其他点可匹配)
			{
				j与x匹配成功;
			}
		}
	}
	遍历了x所有连接点，匹配失败;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

代码模板：

#include <iostream>
#include <string.h>

using namespace std;

const int N = 510, M = 100010;
int head[N], e[M], ne[M], idx;
int match[N];
bool st[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = head[a];
    head[a] = idx++;
}

bool _find(int x)
{
    for (int i = head[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || _find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int n1, n2, m;
    cin >> n1 >> n2 >> m;

    memset(head, -1, sizeof(head));

    while (m --)
    {
        int a, b;
        cin >>a >> b;
        add(a, b);
    }

    int res = 0;
    for (int i = 1; i <= n1; i++)
    {
        memset(st, 0, sizeof(st));
        if (_find(i)) res++;
    }

    printf("%d\n", 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
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

四数学

4.1 关于素数

4.1.1 素数判定

思路：试除法判断素数
时间复杂度：O(sqrt(n))
题目：acwing866
算法模板：

bool IsPrimes(int n)
{
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
1
2
3
4
5
6
7
8
9

4.1.2 分解质因数

思路：n中最多只有一个质因子大于sqrt(n)
时间复杂度：O(sqrt(n))
题目：acwing867
算法模板：

void get_primes(int n)
{
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            int s = 0;
            while (n % i == 0)
            {
                n /= i;
                s++;
            }
            printf("%d %d\n", i, s);
        }
        if (n == 1) break;
    }

    if (n > 1) printf("%d 1\n", n);
    puts("");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.1.3 埃及筛法

思路：每次筛去素数的倍数，把剩下的数（也即素数）保留下来
时间复杂度：O(nloglogn)
题目：acwing868
算法模板：

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            for (int j = i + i; j <= n; j = j + i)
                st[j] = true;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

4.1.4 线性筛法

思路：每个合数n只会被最小的质因子筛掉
模板：

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

4.2 关于约数

4.2.1 求约数

思路：使用试除法求n的所有约数
复杂度：O(sqrt(n))
题目：acwing869
模板：

vector <int> get_factor(int n)
{
    vector <int> res;
    for (int i = 1; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            res.push_back(i);
            if (i * i != n) res.push_back(n / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.2.2 约数个数

思路：

将n分解质因数n = p1^alpha1 + p2^alpha2 + ... + pk^alphak
n的因数是质因数的任意组合，所以因数个数m = (alpha1 + 1)(alpha2 + 1)...(alphak + 1)
1
2

题目：acwing870
模板：

const int mod = 1e9 + 7;
typedef long long LL;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;
    while (n--)
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i++)
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++;
            }
        }

        if (x > 1) primes[x]++;
    }

    LL res = 1;
    for (auto prime : primes)
    {
        res = res * (prime.second + 1) % mod;
    }

    printf("%lld\n", 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
23
24
25
26
27
28
29
30
31
32
33
34
35

4.2.3 约数之和

思路：

将n分解质因数n = p1^alpha1 + p2^alpha2 + ... + pk^alphak
n的因数是质因数的任意组合，所以因数之和:
total = (p1^0 + p1^1 + ... + p1^alpha1)...(pk^0 + pk^1 + ... + pk^alphak)
1
2
3

题目：acwing871
模板：

const int mod = 1e9 + 7;
typedef long long LL;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;
    while (n--)
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i++)
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++;
            }
        }

        if (x > 1) primes[x]++;
    }

    LL res = 1;
    for (auto prime : primes)
    {
        LL fa = prime.first, e = prime.second, t = 1;
        for (int i = 0; i < e; i++)
            t = (t * fa + 1) % mod;
        res = (res * t) % mod;
    }

    printf("%lld\n", 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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

4.2.4 最大公约数（欧几里得算法）

思路：

辗转相除：(a, b) = (b, a mod b)
1

题目：acwing872
模板：

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
1
2
3
4

4.3 欧拉函数

意义：fai(n)表示 1~n 之间与 n 互质的数的个数
公式：phi(n) = n(1 - 1/p1)(1 - 1/p2)…(1 - 1/pk)
证明：利用容斥原理，在 1~n 中去掉 p1, p2, … , pk 的所有倍数。它们都是与 n 不互质的（没有想通为什么？）
题目：acwing873
模板：

int main()
{
    int n;
    cin >> n;

    while (n--)
    {
        int a;
        cin >> a;
        int res = a;
        for (int i = 2; i <= a / i; i++)
        {
            if (a % i == 0)
            {
                res = res / i * (i - 1);
                while (a % i == 0)
                {
                    a /= i;
                }
            }
        }

        if (a > 1) res = res / a * (a - 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
27
28

4.3.1 线性筛法求欧拉函数

思路：

针对线性筛法的if分支分情况讨论：
（1）i是素数，phi(i) = i - 1;
（2）i % pj == 0, pj是i的质因子，所以 pj*i 的质因子和 i 的质因子底数是完全相同的。
区别仅在指数，而指数与欧拉函数无关。推导可得 phi(pj * i) = phi(i) * pj;
（3）i % pj != 0, pj 是 pj*i 的质因子，但不是 i 的质因子。因此 phi(pj * i) 仅比phi(pj)多了一项 pj。
推导可得 phi(pj * i) = phi(i)*(pj - 1);
1
2
3
4
5
6

题目：acwing874
模板：

int primes[N], cnt;
int phi[N];
bool st[N];

LL get_eulers(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }

        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }

    LL res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += phi[i];
    }
    return res;
}
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

4.3.2 欧拉函数的应用（欧拉定理）

定义：

若 a 与 n 互质，则 a^phi(n) mod n = 1。也即a^phi(n)与1模n同余；
进一步引申，当 n 为质数时，成为费马定理：a^phi(p - 1) mod p = 1， a^phi(p - 1)与1模p同余。
1
2

4.4 快速幂

算法：

应用场景：快速求解 a^k mod p
时间复杂度是：O(logk)
预先求出 a^(2^0), a^(2^1), a^(2^2), ..., a^(2^logk)，可以发现当前项总是前项的平方；
a^k 写成 a^(2^i) 的乘积，即把 k 写成2的指数次幂和，二进制划分的结果。
从而快速求出 a^k
1
2
3
4
5

题目：acwing875
模板：

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1 == 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k = k >> 1;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11

4.4.1 快速幂求逆元

题目：acwing876
思路：

利用费马定理和逆元定义推导出逆元计算公式：b^(-1) = b^(m - 2)(mod m);
利用快速幂求解如下：qmi(b, p - 2, p);
只有当b是m的倍数时b的逆元是不存在的，因为 b * b^(-1) mod m = 0。
1
2
3

4.5 扩展欧几里得算法

题目：acwing877, acwing878
思路：

求x, y使其满足 a*x + b*y = (a, b);
通过在gcd函数递归的过程中传进 x, y实现。
1
2

模板：

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);
    y = y - a / b * x;
    return d;
}
1
2
3
4
5
6
7
8
9
10
11
12

4.6 高斯消元法解方程

思路：

模拟行列式求解的过程；
枚举每一列c，找出最大行，换行，行首变成1，把第c列消成0；
消元结果倒推求出方程的解。
1
2
3

题目：acwing883
模板：

const int N = 110;
const double eps = 1e-6;
double a[N][N];
int n;

int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c++)
    {
        int t = r;
        for (int i = r + 1; i < n; i++)
        {
            if (fabs(a[t][c]) < fabs(a[i][c]))
                t = i;
        }

        if (fabs(a[t][c]) < eps) continue;

        if (t != r)
            for (int i = c; i <= n; i++)
                swap(a[r][i], a[t][i]);
        for (int i = n; i >= c; i--)
            a[r][i] /= a[r][c];
        for (int i = r + 1; i < n; i++)
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j--)
                    a[i][j] -= a[i][c] * a[r][j];

        r++;
    }

    if (r < n)
    {
        for (int i = r; i < n; i++)
        {
            if (fabs(a[i][n]) > eps)
                return 2;
        }

        return 1;
    }

    for (int i = n - 2; i >= 0; i--)
    {
        for (int j = i + 1; j < n; j++)
            a[i][n] = a[i][n] - a[i][j] * a[j][n];
    }

    return 0;
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= n; j++)
            scanf("%lf", &a[i][j]);

    int t = gauss();
    if (t == 0)
    {
        for (int i = 0; i < n; i++)
            printf("%.2lf\n", a[i][n]);
    }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");

    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
68
69
70
71

4.7 组合数

4.7.1 组合数1

应用场景：

询问次数多，而询问空间小；
例如，询问100000次，C(a, b)中0 <= a, b <= 2000，组合数范围是2000^2；
采用预处理所有组合数的策略，使用递推公式：C(a, b) = C(a - 1, b) + C(a - 1, b - 1)。
C(a, 0) = 1;
1
2
3
4

题目：acwing885
模板：

const int N = 2010, mod = 1e9 + 7;
int c[N][N];

void init()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= i; j++)
        {
            if (!j) c[i][j] = 1;
            else
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.7.2 组合数2

应用场景：

询问次数多，而询问空间小；
例如，询问100000次，C(a, b)中0 <= a, b <= 100000；
采用预处理阶乘和阶乘逆元的策略，使用阶乘公式求：C(a, b) = a! / ((a - b)! * b!)。
fact(0) = infact(0) = 1;
因为mod是质数，所以可以用快速幂求对于mod的逆元。
1
2
3
4
5

题目：acwing886
模板：

const int N = 100010, mod = 1e9 + 7;
int fact[N], infact[N];

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1 == 1)
        {
            res = (LL)res * a % p;
        }
        a = (LL)a * a % p;
        k  = k >> 1;
    }
    return res;
}

void init()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

int main()
{
    init();

    int n, a, b;
    scanf("%d", &n);

    while (n--)
    {
        cin >> a >> b;
        printf("%lld\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    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

4.7.3 组合数3

应用场景：

询问次数多，而询问空间小；
例如，询问20次，C(a, b)中1 <= a, b <= 1e18;
使用lucas定理：C(a, b) 同余于 C(a mod p, b mod p) * C(a / p, b / p) (mod p);
其中式子第一项可以直接用定义求，式子第二项用lucas定理递归求。
1
2
3
4

题目：acwing887
模板：

int p;

int qmi(int a, int k, int q)
{
    int res = 1;
    while (k)
    {
        if (k & 1 == 1)
        {
            res = (LL)res * a % q;
        }
        a = (LL)a * a % p;
        k = k >> 1;
    }
    return res;
}

int C(int a, int b)
{
    int res = 1;
    for (int i = 1, j = a; i <= b; i++, j--)
    {
        res = (LL)res * j * qmi(i, p - 2, p) % p;
    }
    return res;
}

int lucas(LL a, LL b)
{
    if ( a < p && b < p) return C(a, b);
    else return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main()
{
    int n;
    cin >> n;

    while (n--)
    {
        LL a, b;
        cin >> a >> b >> p;

        cout << lucas(a, b) << 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

4.7.4 组合数4

应用场景：

求组合数的高精度结果，不取模；
首先将 a!, b!, (a - b)!分解质因数，例：a!对于素数p的次数为 a/p + a/(p^2) + ...；
最后把所有质因数采用高精度乘法相乘。
1
2
3

题目：acwing888

const int N = 5010;
int primes[N], cnt;
bool st[N];
int sum[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int get(int n, int p)
{
    int res = 0;
    while (n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}

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[c.size() - 1] == 0) c.pop_back();

    return c;
}

int main()
{
    int a, b;
    cin >> a >> b;

    get_primes(a);

    for (int i = 0; i < cnt; i++)
    {
        int j = primes[i];
        sum[i] = get(a, j) - get(b, j) - get(a - b, j);
    }

    vector<int> ans;
    ans.push_back(1);

    for (int i = 0; i < cnt; i++)
        for (int j = 0; j < sum[i]; j++)
        {
            ans = mul(ans, primes[i]);
        }

    for (int i = ans.size() - 1; i >= 0; i--)
        printf("%d", ans[i]);

    puts("");
    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
68
69
70
71
72
73

4.8 卡特兰数

应用场景：

很多问题的方案数都是卡特兰数；
C(2n, n) - C(2n, n - 1) = C(2n, n) / n + 1;
求逆元有两种方式：如果模数是素数，可以用快速幂求解；如果不是素数，要用扩展欧几里得算法求解。
1
2
3

题目：awing889
模板：

const int mod = 1e9 + 7;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1 == 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k = k >> 1;
    }
    return res;
}

int main()
{
    int n;
    cin >> n;

    int a = 2 * n, b = n;
    int res = 1;
    for (int i = a; i > a - b; i--)
        res  = (LL)res * i % mod;

    for (int i = 1; i <= n; i++)
        res = (LL)res * qmi(i, mod - 2, mod) % mod;

    res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;
    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
27
28
29
30
31
32

4.9 容斥原理

思路：

求集合|S|，用 n/p 来求个数；
容斥原理公式一共有 2^m 项，使用位运算来枚举所有情况。
1
2

题目：acwing890
模板：

const int M = 20;
int n, m, p[M];


int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> p[i];

    int res = 0;
    for (int i = 1; i < 1 << m; i++)
    {
        int t = 1, cnt = 0;
        for (int j = 0; j < m; j++)
        {
            if (i >> j & 1)
            {
                cnt++;
                if ((LL)t * p[j] > n)
                {
                    t = -1;
                    break;
                }
                t *= p[j];
            }
        }

        if (t != -1)
        {
            if (cnt % 2)
                res += n / t;
            else
                res -= n / t;
        }
    }

    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
27
28
29
30
31
32
33
34
35
36
37
38
39
40

4.10 博弈论

4.10.1 Nim游戏

结论：

异或：a1^a2^...^am = 0 先手必败；不等于0 先手必胜。
1

题目：acwing891
题解：

int main()
{
    int n;
    cin >> n;

    int res = 0;
    while (n--)
    {
        int x;
        cin >> x;
        res ^= x;
    }

    if (res) puts("Yes");
    else puts("No");

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

五动态规划

5.1 背包问题

5.1.1 01背包

描述：每件物品只有1个
题目：acwing2
思考方式：

Dp
（1）状态表示 f(i, j)
	（(1)）集合
			（((1))）所有的选法
			（((2))）满足条件：只从前 i 个物品中选择；总体积 < j
	（(2)）属性：max，min，数量
（2）状态的计算 —— 集合划分：不包含 i 和包含 i，两种情况。使问题逐步趋近结果。
1
2
3
4
5
6
7

题解：

// 朴素二维
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;
    return 0;
}

// 优化一维
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
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

5.1.2 完全背包

描述：每件物品有无数个
思路：

(1) dp状态转移方程f(i, j) = max(f(i - 1, j), f(i - 1, j - v) + w, f(i - 1, j - 2v) + 2w,
 ..., f(i - 1, j - kv) + kw)
(2) f(i, j - v) = max(f(i - 1, j - v), f(i - 1, j - 2v) + w, ..., f(i - 1, j - kv) + kw)
所以，f(i, j) = max(f(i - 1, j), f(i, j - v) + w)
1
2
3
4

题目：acwing3
题解：

// (1)朴素做法
int v[N], w[N];
int f[N][N];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            for (int k = 1; k * v[i] <= j; k++)
            {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k*w[i]);
            }
        }

    cout << f[n][m] << endl;
    return 0;
}

// (2)递推优化
   for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (v[i] <= j) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

// (3)f优化到1维
int v[N], w[N];
int f[N];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << 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

5.1.3 多重背包

描述：每件物品有 si 个
题目：acwing4、acwing5
思路：

从dp问题的状态表示和状态计算两方面考虑。
（1）f(i, j) = max(f(i-1,j-kv)+kw), k属于[0,s[i]]
（2）把s[i]件物品i打包成logs[i]件，即1，2，4，……，2^logs[i]，c。打包后的物品只有1件，看成01背包问题
1
2
3

题解：

// (1)朴素做法O(n*m*m)
int v[N], w[N], s[N];
int f[N][N];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            for (int k = 1; k * v[i] <= j && k <= s[i]; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }

    cout << f[n][m] << endl;
    return 0;
}

// (2)二进制优化O(n*logs*m)
const int N = 15000, M = 2000;

int v[N], w[N];
int f[M];
int n, m;

int main()
{
    cin >> n >> m;
    int cnt = 1;
    for (int i = 0; i < n; i++)
    {
        int a, b, s;
        cin >> a >> b >> s;

        int k = 1;
        while (k <= s)
        {
            v[cnt] = k * a;
            w[cnt] = k * b;
            cnt++;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            v[cnt] = s * a;
            w[cnt] = s * b;
            cnt++;
        }
    }

    for (int i = 1; i < cnt; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << 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

5.1.4 分组背包

描述：将物品分组，每组限制拿取种类
思路：

考虑状态计算时，参考多重背包的朴素枚举思路，枚举第i组中物品选哪个。
f(i,j)=max(f(i-1,j),f(i-1,j-v[i,k])+w[i,k])
1
2

题目：acwing9
题解：

const int N = 110;
int v[N][N], w[N][N], s[N];
int f[N];

int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 0; j--)
            for (int k = 1; k <= s[i]; k++)
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << 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

5.2 线性DP

线性DP：以每行或者每列考虑问题的结果，使得动态规划像线性一样。
时间复杂度分析：状态数量（状态表示的维度）* 状态转移的花销
求目标方案：就是把状态转移存下来，方便回溯
题目：数字三角形
题解：

const int N = 510, INF = 1e9;
int a[N][N];
int f[N][N];

int n;

int main()
{
    cin >> n;
    for (int i = 1; i <=n; i++)
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= i + 1; j++)
            f[i][j] = -INF;

    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];

    int res = f[n][1];
    for (int i = 2; i <= n; i++) res = max(res, f[n][i]);
    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
27

题目：最长上升子序列
思路：

状态表示：f(i)表示所有以 i 结尾的子序列的选择，将其中最大的子序列长度存储下来。
状态转移：把 f(i) 划分成 i 种情况。f(i) = Max(f(j) + 1), a[j] < a[i], j = 0, 1, 2, …, i-1

题解：

const int N = 1010;

int a[N], f[N];
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[i]);
    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

题目：最长公共子序列
思路：

状态表示：f(i, j) 所有第一个序列前 i 个字母和第二个序列前 j 个字母中的公共子序列的最大长度。
状态计算：f(i, j) 被划分成四种情况，包含与否 a(i), b(j) 。f(i, j) = max(f(i - 1, j), f(i, j - 1), f(i - 1, j - 1) + 1)。求Max状态划分可以重叠。

题解：

char a[N], b[N];
int f[N][N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a+1, b+1);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }

    printf("%d\n", f[n][m]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度：O(n^2) 。状态表示为 n^2 ，状态计算是 O(1) 。
题目：编辑距离。状态表示和 最长公共子序列 很相似。

5.3 区间DP

题目：石子合并
分析：

状态表示： f(i, j) 是所有的将从第 i 堆石子到第 j 堆石子的合并方式的最小值。
状态计算： f(i, j) 以两堆石子分割线位置被划分。从 i+1 到 j-1 的位置，计为 k。 f(i,j)=Min(f(i,k)+f(k+1,j)+s[j]-s[i-1])

题解：

const int N = 310;

int s[N];
int f[N][N];
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &s[i]);

    for (int i = 1; i <= n; i++)
        s[i] = s[i] + s[i - 1];

    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int l = i, r = i + len - 1;
            f[l][r] = 1e9;
            for (int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l-1]);
        }

    printf("%d\n", f[1][n]);
    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

时间复杂度： O(n^3)

5.4 计数类DP

题目：整数划分
思路：从完全背包的角度考虑。

状态表示 f(i, j) 表示 1-i 共 i 件商品体积和恰好是 j 的所有选法数量。
状态计算 f(i, j)=f(i-1, j)+f(i, j - 1) 。

题解：

const int N = 1010, mod = 1e9+7;

int f[N];
int n;

int main()
{
   scanf("%d", &n);

   f[0] = 1;
   for (int i = 1; i <= n; i++)
       for (int j = i; j <= n; j++)
       {
           f[j] = (f[j] + f[j - i]) % mod;
       }

   cout << f[n] << endl;
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5.5 计数位DP

题目：acwing338
思路：实现一个count(n, x)函数表示在 1-n 中数字 x 出现的次数，最后用前缀和的方式计算最终结果count(j, x) - count(i-1, x)。关键点是分情况讨论，求出 x 在每一位上的出现次数。
难点： 充分讨论 x 是否等于 0 ，以及当前数值位 d 与 x 的大小关系。
题解：

int a, b;

int get(vector<int> num, int l, int r)
{
    int res = 0;
    for (int i = l; i >= r; i--)
    {
        res = res*10 + num[i];
    }
    return res;
}

int power10(int x)
{
    int res = 1;
    while(x)
    {
        res *= 10;
        x--;
    }
    return res;
}

int count0(int n, int x)
{
    vector<int> num;
    while (n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();

    int res = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        if (!x && i == n - 1) continue; //x == 0时最高位不放

        if (i < n - 1)
        {
            res += get(num, n - 1, i + 1)*power10(i);
            if (!x) res -= power10(i);
        }

        if(num[i] > x) res += power10(i);
        else if (num[i] == x) res += get(num, i - 1, 0) + 1;
    }
    return res;
}

int main()
{
    while (true)
    {
        cin >> a >> b;
        if (a == 0 && b == 0)
            break;
        if (a > b) swap(a, b);

        for (int i = 0; i < 10; i++)
            cout << count0(b, i) - count0(a - 1, i) << " ";
        cout << 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

5.6 状态压缩DP

题目：acwing291
思路：找出横向小方格的所有选法，纵向小方格的放置是唯一的。 f(i, j) 表示第 i 列处于 j（用二进制位运算表示该列所有放置状态） 放置方式下的所有放法。f(i,j) = f(i-1,0) + f(i-1,1) + … + f(i-1,m)。满足要求的策略应该具备，j 是当前列的一种放置策略，k 是 i-1 列的各种情况遍历：

（1）j&k == 0前后两列不存在冲突；
（2）j|k不存在连续奇数个0。

写代码的时候先预处理，检查所有状态，筛选出满足要求的状态。

const int N = 12, M = 1 << N;
long long f[N][M];
bool st[M];
int n, m;

int main()
{
    while (true)
    {
        scanf("%d%d", &n, &m);
        if (n == 0 && m == 0)
            break;

        // 预处理 2^n 种状态的可行结果
        memset(f, 0, sizeof(f));

        for (int i = 0; i < 1 << n; i++)
        {
            st[i] = true;
            int cnt = 0;
            for (int j = 0; j < n; j++)
                if (i >> j & 1)
                {
                    if (cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else
                    cnt++;
            if (cnt & 1) st[i] = false;
        }

        f[0][0] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 0; j < 1 << n; j++)
                for (int k = 0; k < 1 << n; k++)
                {
                    if ((j & k) == 0 && st[j|k])
                        f[i][j] += f[i - 1][k];
                }

        printf("%lld\n", f[m][0]); // 最后一列没有方块怼出去
    }
    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

题目：acwing91最短哈密顿距离
思路：

f(i, j) 表示所有从 0 走到 j 经过的所有点是 i 的路径。i 采用二进制状态压缩表示 n 个结点是否被经过，共有 2^n 种状态。
状态计算，根据路径中倒数第2个点进行分类，f(i,j) = Min(f(i-{j},k) + w(k,j) k 是从 0 开始枚举的。

题解：

const int N = 22, M = 1 << N;
int g[N][N];
int f[M][N];
int n;

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            int w;
            cin >> w;
            g[i][j] = w;
        }

    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;

    for (int i = 1; i < 1 << n; i++)
        for (int j = 1; j < n; j++)
        {
            if (i >> j & 1) // 从0走到j点的状态
            {
                for (int k = 0; k < n; k++)
                    if ((i - (1 << j)) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + g[k][j]);
            }
        }

    cout << f[(1 << n) - 1][n - 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

5.7 树形DP

题目：acwing285没有上司的舞会
思路：

状态表示 f(u,0)和f(u,1) 分别表示以 u 为根结点的子树包含和不包含 u 的情况下的 Max 值。
状态计算 f(u,0) = 求和(max(f(Si,0),f(Si,1))); f(u,1) = 求和(f(Si,0))。

题解：

const int N = 6010;
int happy[N];
int f[N][2];
int h[N], e[N], ne[N], idx;
int n;
bool has_father[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];

        dfs(j);

        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &happy[i]);

    memset(h, -1, sizeof(h));
    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        has_father[a] = true;
    }

    int u = 1;
    while (has_father[u]) u++;

    dfs(u);

    printf("%d\n", max(f[u][0], f[u][1]));
    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

5.8 记忆化搜索

题目：acwing901滑雪
思路：

状态表示 f(i, j) 表示以 (i, j) 为起点的所有滑雪方式的 Max 值。
状态计算 f(i,j) = max(f(i-1,j), f(i,j+1), f(i+1,j), f(i,j-1))。
使用递归实现。

题解：

const int N = 310;

int ha[N][N];
int f[N][N];
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x, int y)
{
    int &v = f[x][y];
    if (v != -1) return v;

    v = 1;
    for (int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= m && b >= 1 && b <= n && ha[a][b] < ha[x][y])
            v = max(v, dp(a, b) + 1);
    }

    return v;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &ha[i][j]);

    memset(f, -1, sizeof(f));

    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            res = max(res, dp(i, j));
    printf("%d\n", 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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

六贪心

6.1 区间问题

题目： 区间选点acwing905、最大不相交区间数量acwing908
思路：

（1）将所有区间按照右端点从小到大排序；
（2）从前往后依次枚举每个区间。如果当前区间包含选择点，pass。否则选择当前区间的右端点。

代码：

const int N = 100010;

struct Range
{
    int l, r;
    bool operator <(const Range &W)const
    {
        return r < W.r;
    }
}range[N];

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range+n);

    int cnt = 0, end0 = -2e9;
    for (int i = 0; i < n; i++)
    {
        if (range[i].l > end0)
        {
            cnt++;
            end0 = range[i].r;
            printf("%d\n", end0);
        }
    }

    printf("%d\n", cnt);
    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

题目： 区间分组acwing906
思路：

所有区间按左端点从小到大排序；
从前往后处理每个区间，判断能否放进某个组中。如果不存在这样的组，满足L[i] <= Min(Max_r)，开进组，把该区间放进去。否则，把区间放到满足条件的组，更新 Max_r。

代码：

const int N = 100010;

struct Range
{
    int l, r;
    bool operator< (const Range& W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range + n);

    priority_queue <int, vector<int>, greater<int> > heap;

    for (int i = 0; i < n; i++)
    {
        if (heap.empty() || heap.top() >= range[i].l)
        {
            heap.push(range[i].r);
        }
        else
        {
            heap.pop();
            heap.push(range[i].r);
        }
    }

    printf("%lld\n", heap.size());
    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

题目： 区间覆盖acwing907
思路：

所有区间按左端点从小到大排序；
从前往后枚举每个区间。在所有能覆盖start的区间中，选出右端点最大的区间；
将start设置成选出区间的右端点。

代码：

const int N = 100010;

struct Range
{
    int l, r;
    bool operator <(const Range &W)const
    {
        return l < W.l;
    }
}range[N];

int n;

int main()
{
    int st, ed;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range+n);

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st)
        {
            r = max(r, range[i].r);
            j++;
        }

        if (r < st)
        {
            res = -1;
            break;
        }

        res++;
        st = r;
        i = j - 1;

        if (r >= ed)
        {
            break;
        }
    }

    printf("%d\n", 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
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

6.2 哈夫曼树

题目： acwing148合并果子
代码：

int main()
{
    int n;
    scanf("%d", &n);

    priority_queue<int, vector<int>, greater<int> > heap;

    while (n--)
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }

    printf("%d\n", 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
23
24
25
26
27

6.3 打水问题

题目：acwing913排队打水
思路： 按照打水时间从小到大排队，总时间最小。
代码：

int n;
int t[N];

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &t[i]);
    }

    sort(t, t + n);

    LL res = 0;

    for (int i = 0; i < n; i++)
        res += t[i] * (n - i - 1);

    printf("%lld\n", 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
23

6.4 绝对值不等式

题目：acwing104货仓选址
思路：

把所有货舱点从小到大排列在数轴上；
f(x) = |x1-x| + |x2-x| + … + |xn-x| = (|x1-x|+|xn-x|) + (|x2-x|+|xn-1 - x|) + …
当 x 选在 x1、xn 中间时，(|x1-x|+|xn-x|) 取得最小值xn-x1。因此取序列中位数作为 x 点，是最优解。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int t[N];

int main()
{
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++)
        scanf("%d", &t[i]);
    
    sort(t, t + n);
    
    int res = 0;
    for (int i = 0; i < n; i++)
        res += abs(t[i] - t[n / 2]);
    
    printf("%d\n", 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
23
24
25
26
27

6.5 耍杂技的牛（推公式

题目：acwing125
思路：

按照 wi+si 从小到大排序，得到的最大危险系数一定最小。
通过调整法进行证明：假设最优解不按照 wi+si 从小到大排序，则一定存在 wi+si > w(i+1)+s(i+1) 。推出 i 位置和 i+1 位置的危险系数公式，能够得出交换后最大危险系数变小的结论。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

PII niu[N];
int n;

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        int w, s;
        scanf("%d%d", &w, &s);
        niu[i] = {w + s, w};
    }

    sort(niu, niu + n);

    int res = -2e9, sum = 0;
    for (int i = 0; i < n; i++)
    {
        int w = niu[i].second, s = niu[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }

    printf("%d\n", 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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

七时空复杂度分析

时间复杂度基本常识： 根据数据范围推测算法。一般题目允许的计算次数在 10^7 ~ 10^8。
时间复杂度分析常用方法（模型）：

分析循环
递归，每一层的计算量 * 递归层数。例如，快排、归并排序，O(n)*logn。
双指针、单调栈、单调队列、KMP，表面上看是两层循环，但是内层循环只加不减，是线性的。
并查集，nlogn。
遍历图，DFS和BFS，先对 n 个点判重，然后每条边仅遍历一次，所以n+m。
动态规划问题，状态数量*状态转移计算量。也可以根据循环计算。

空间复杂度分析：

int 4 Byte; char 1 Byte; double, long long 8 Byte 
1 Byte = 8 bit
1 KB = 1024 Byte
1 MB = 1024 * 1024 Byte
1 GB = 1024 * 1024 * 1024 Byte
64M = 2^26 Byte = 2^24 int ~= 16000000 int
1
2
3
4
5
6

根据题目给的空间限制可以推算，开数组空间的最大值；
也可以用 sizeof 直接计算数组空间。

结尾

学了好长时间的算法基础课，中途停下来好几次，终于跟完了所有视频。但是还是要说，算法基础只是开始，未来还有很长的路要走。感谢看到这里！

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】

【算法】基础算法学习总结_逆序对博弈

目录

一、基础算法

1.1 排序

快速排序

【模板题】快速排序

第k个数

归并排序

逆序对

1.2 二分

【模板题】数的范围

浮点数二分

1.3 高精度

高精度存储

加法

减法

高精度x低精度

高精度 / 低精度

1.4 前缀和及差分

一维前缀和

二维前缀和

差分

二维差分

1.5 双指针算法

1.6 位运算

1.7 离散化

模板

1.8 区间合并

二、数据结构

2.1 数组模拟链表

2.2 双向链表

2.3 栈

2.4 队列

2.5 单调栈

2.6 单调队列

2.7 KMP

2.8 Trie树

2.9 并查集

2.10 堆

2.11 整数哈希表

（1）拉链法

（2）开放寻址法

2.12 字符串哈希

2.13 STL

2.14 素数筛选

三 搜索

3.1 DFS

3.2 BFS

3.3 图的存储

3.4 最短路算法

3.4.1 朴素Dijkstra

3.4.2 堆优化Dijkstra

3.4.3 bellman_ford算法

3.4.4 spfa算法

3.4.5 floyd算法

3.5 最小生成树

3.5.1 Prim算法

3.5.2 Kruskal算法

3.6 二分图

3.6.1 染色法

3.6.2 匈牙利算法

四 数学

4.1 关于素数

4.1.1 素数判定

4.1.2 分解质因数

4.1.3 埃及筛法

4.1.4 线性筛法

4.2 关于约数

4.2.1 求约数

4.2.2 约数个数

4.2.3 约数之和

4.2.4 最大公约数（欧几里得算法）

4.3 欧拉函数

4.3.1 线性筛法求欧拉函数

4.3.2 欧拉函数的应用（欧拉定理）

4.4 快速幂

4.4.1 快速幂求逆元

4.5 扩展欧几里得算法

4.6 高斯消元法解方程

4.7 组合数

三搜索

四数学

五动态规划

六贪心

七时空复杂度分析