快速排序

图解分析：

img点击并拖拽以移动

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//核心思想：分而治之
//函数参数：(需要处理的数组， 数组的左边界， 数组的右边界)
//函数：使得左边小于x, 右边大于x
 void quick_sort(int q[], int l, int r)
{
    //递归出口
    if (l >= r) return;
    
    //运用双指针，左指针指向的数小于x, 右指针指向的数大于x
    int x = (q[l] + q[r]) / 2;
    int i = l - 1, j = r + 1;
    while (i < j)
    {
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    
    //递归处理左右子区间
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

点击并拖拽以移动

大概思路：

​ 1.分成子问题：将数组分为左边小于x， 右边大于x
​ 2.递归处理子问题：递归处理左右子区间
​ 3.子问题合并

快速排序例题（C++版）：

Acwing785.快速排序

img点击并拖拽以移动 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    
    int x = (q[l] + q[r]) / 2;
    int 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);
}
int main()
{
    int n;
    int q[N];
    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]);
}

点击并拖拽以移动

Acwing786.第k个数img点击并拖拽以移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return ;
    
    int x = (q[l] + q[r]) / 2;
    int 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);
}
int main() 
{
    int q[N];
    int n, k;
    scanf ("%d %d", &n, &k);
    
    for (int i = 0; i < n; i ++ )
        scanf("%d", &q[i]);
        
    quick_sort(q, 0, n - 1);
    
    printf("%d\n", q[k - 1]);
}

点击并拖拽以移动

归并排序

图解分析：

img点击并拖拽以移动

模板：

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
//核心思想：分而治之
//函数参数:(需要处理的数组， 数组左边界， 数组右边界)
//函数:使得以mid下标两侧的区间有序
void merge_sort(int q[], int l, int r)
{
    //递归出口
    if (l >= r) return ;
    //分成左右子区间:使得左右两个区间有序
    int mid = (l + r) / 2;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    
    //合并左右子区间
    int i = l;
    int j = mid + 1;
    int 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 (int i = 0, j = l; i < k; i ++, j ++) q[j] = tmp[i];
}

点击并拖拽以移动

大概思路：

​ 1.分成子问题：以mid为分界线的左右区间有序
​ 2.递归处理子问题：递归处理左右子区间
​ 3.子问题合并：将左右区间有序数组合并

归并排序例题（C++版）：

Acwing787.归并排序

img点击并拖拽以移动 

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int tmp[N];

void merge_sort(int q[], int l, int r)
{
    //递归出口
    if (l >= r) return ;
    //分成子问题
    int mid = (l + r) / 2;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    
    //合并
    int i = l;
    int j = mid + 1;
    int 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 (int i = 0, j = l; i < k; i ++, j ++) q[j] = tmp[i];
}
int main()
{
    int q[N];
    int n;
    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]);
}

点击并拖拽以移动

Acwing788.逆序对的数量img点击并拖拽以移动

解析：

img点击并拖拽以移动 

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
typedef long long LL;
int q[N], tmp[N];
LL len;
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return ;
    
    int mid = (l + r) / 2;
    merge_sort (q, l, mid);
    merge_sort (q, mid + 1, r);
    
    int i = l;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else
        {
            tmp[k ++] = q[j ++];
            len += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    
    for (int i = 0, j = l; i < k; i ++, j ++ ) q[j] = tmp[i];
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);
    printf("%lld\n", len);
}

点击并拖拽以移动

二分查找

图解分析：

img点击并拖拽以移动

模板：

从左边开始找：

1
2
3
4
5
6
7
8
int l = 0;
int r = n - 1;
while (l < r)
{
     int mid = (l + r) / 2;
     if (a[mid] >= x) r = mid;
     else l = mid + 1;
}

点击并拖拽以移动

从右边开始找：

1
2
3
4
5
6
7
8
l = 0;
r = n - 1;
while(l < r)
{
    int mid = (l + r + 1) / 2;
    if (a[mid] <= x) l = mid;
    else r = mid - 1;
}

点击并拖拽以移动

大概思路：

​ 根据a[mid]与x的大小关系，不断更新左右区间

当从右边开始找时，对于mid=(l+r+1)的说明：

​ 当 l 和 r 相邻时（即 r = l + 1），使用 (l + r) / 2 计算得到的 mid 会等于 l（因为整数除法向下取整）。如果条件判断使得 l 更新为 mid，那么实际上 l 没有发生变化，导致 l 和 r 始终保持相邻状态，形成死循环。通过将 mid 的计算公式改为 (l + r + 1) / 2，可以确保 mid 等于 r，从而在下一次迭代中可以正确地更新 l 或 r，避免死循环。

二分法例题（C++版）：

Acing789.数的范围

img点击并拖拽以移动 

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

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

点击并拖拽以移动

Acwing790.数的三次方根

img点击并拖拽以移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>

using namespace std;

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

点击并拖拽以移动

高精度运算

加法：

核心思想：

​ 1.将数字当成字符串读入

​ 2.字符串转换成数组(从低位向高位)

​ 3.数组每个数字相加(注意有进位)

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> add(vector<int> x, vector<int> y)
{
    vector<int> res; //存储加法结果
    if (x.size() < y.size()) return add(y, x);
    int t = 0;
    for (int i = 0; i < x.size(); i ++ )
    {
        t += x[i];
        if (i < y.size()) t += y[i];
        res.push_back(t % 10);
        t /= 10;
    }
    if (t) res.push_back(t);
    return res;
}

点击并拖拽以移动

高精度加法例题：

Acwing791.高精度加法

img点击并拖拽以移动

C++: 

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

vector<int> add(vector<int> x, vector<int> y)
{
    vector<int> res; //存储加法结果
    if (x.size() < y.size()) return add(y, x);
    int t = 0;
    for (int i = 0; i < x.size(); i ++ )
    {
        t += x[i];
        if (i < y.size()) t += y[i];
        res.push_back(t % 10);
        t /= 10;
    }
    if (t) res.push_back(t);
    return res;
}
int main()
{
    vector<int> x, y;
    string a, b;
    cin >> a >> b;
    
    for (int i = a.size() - 1; i >= 0; i -- ) x.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) y.push_back(b[i] - '0');
    
    vector<int> res = add(x, y);
    for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
        
}

点击并拖拽以移动

C: 

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
#include <stdio.h>
#include <string.h>
#include <math.h>

#define N 100010

char a[N], b[N];
int x[N], y[N];
int la, lb;
int ans[N];

int add(int x[], int y[])
{
    int t = 0; // 表示进位
    for (int i = 0; i < la || i < lb; i ++)
    {
        int sum = x[i] + y[i] + t; // 当前加数之和
        ans[i] = sum % 10;
        t = sum / 10; // 进位
    }
    return t;
}
int main()
{
    scanf("%s%s", a, b);
    
    la = strlen(a);
    lb = strlen(b);
    
    for (int i = la - 1, t = 0; i >= 0; i --, t ++) x[t] = a[i] - '0';
    for (int i = lb - 1, t = 0; i >= 0; i --, t ++) y[t] = b[i] - '0';
    
    int t = add(x, y); // x + y
    
    if (t) printf("%d", t);
    
    int len = la > lb ? la : lb;
    for (int i = len - 1; i >= 0; i --) printf("%d", ans[i]);
        
    printf("\n");
    return 0;
}

点击并拖拽以移动

减法：

核心思想：

​ 1.将数字按照字符串读入

​ 2.字符串转化为数组

​ 3.比较两个数字大小

​ 4.两个数字相减，大数减小数

​ 5.去掉前导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
//比较x与y的大小
// x >= y 返回true
bool cmp(vector<int> x, vector<int> y)
{
    if (x.size() != y.size()) return x.size() > y.size();
    
    for (int i = x.size() - 1; i >= 0; i -- )
        if (x[i] != y[i]) return x[i] > y[i];
    
    return true;
}
vector<int> sub(vector<int> x, vector<int> y)
{
    vector<int> res;
    
    int t = 0;
    for (int i = 0; i < x.size(); i ++ )
    {
        t = x[i] - t;
        if (i < y.size()) t -= y[i];
        res.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    //前缀0去掉
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

点击并拖拽以移动

高精度减法例题：

Acwing792.高精度减法

img点击并拖拽以移动

C++代码： 

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

//比较x与y的大小
// x >= y 返回true
bool cmp(vector<int> x, vector<int> y)
{
    if (x.size() != y.size()) return x.size() > y.size();
    
    for (int i = x.size() - 1; i >= 0; i -- )
        if (x[i] != y[i]) return x[i] > y[i];
    
    return true;
}
vector<int> sub(vector<int> x, vector<int> y)
{
    vector<int> res;
    
    int t = 0;
    for (int i = 0; i < x.size(); i ++ )
    {
        t = x[i] - t;
        if (i < y.size()) t -= y[i];
        res.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    //前缀0去掉
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}
int main()
{
    string a, b;
    cin >> a >> b;
    
    vector<int> x, y;
    for (int i = a.size() - 1; i >= 0; i -- ) x.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) y.push_back(b[i] - '0');
    
    vector<int> res;
    if (cmp(x, y)) res = sub(x, y);
    else
    {
        cout << '-';
        res = sub(y, x);
    }
    
    for (int i = res.size() - 1; i >= 0; i -- )
        cout << res[i];
        
    return 0;
}

点击并拖拽以移动

C语言代码： 

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
#define N 100010

char a[N], b[N];
int x[N], y[N];
int la, lb;
int ans[N];

int cmp(int x[], int y[])
{
    if (la > lb) return 1;
    else if (lb > la) return -1;
    else
    {
        for (int i = la - 1; i >= 0; i --)
        {
            if (x[i] > y[i]) return 1;
            if (y[i] > x[i]) return -1;
        }
        
        return 0;
    }
}
int remov(int x[], int y[])
{
    int t = 0; // 表示借位
    for (int i = 0; i < la || i < lb; i ++)
    {
        x[i] -= t;
        if (x[i] < y[i]) t = 1; // 借一位
        else t = 0;
        int sum = x[i] - y[i] + t * 10;
        ans[i] = sum % 10;
    }
    return t;
}
int main()
{
    scanf("%s%s", a, b);
    
    la = strlen(a);
    lb = strlen(b);
    
    for (int i = la - 1, t = 0; i >= 0; i --, t ++) x[t] = a[i] - '0';
    for (int i = lb - 1, t = 0; i >= 0; i --, t ++) y[t] = b[i] - '0';
    
    int t = cmp(x, y);
    if (t == 0)
    {
        printf ("0\n");
    }
    else if (t == 1)
    {
        remov(x, y);
        bool flag = true;
        for (int i = la - 1; i >= 0; i --)
        {
            if (ans[i] != 0) flag = false;
            if (flag) continue;
            else printf("%d", ans[i]);
        }
    }
    else
    {
        remov(y, x);
        bool flag = true;
        printf("-");
        for (int i = lb - 1; i >= 0; i --)
        {
            if (ans[i] != 0) flag = false;
            if (flag) continue;
            else printf("%d", ans[i]);
        }
    }
    
    return 0;
}

点击并拖拽以移动

乘法：

核心思想：

​ 1.规模大的数字按照字符串读入

​ 2.将字符串转化为数组

​ 3.将数组中的每一个数与数字相乘

模版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> mul(vector<int> x, int y) 
{
    vector<int> res;
    
    int t = 0;
    for (int i = 0; i < x.size(); i ++ )
    {
        t += x[i] * y;
        res.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        res.push_back(t % 10);
        t /= 10;
    }
    return res;
}

点击并拖拽以移动

高精度乘法例题：

Acwing793.高精度乘法

img点击并拖拽以移动

C++代码： 

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

vector<int> mul(vector<int> x, int y) 
{
    vector<int> res;
    
    int t = 0;
    for (int i = 0; i < x.size(); i ++ )
    {
        t += x[i] * y;
        res.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        res.push_back(t % 10);
        t /= 10;
    }
    return res;
}
int main()
{
    string a;
    int b;
    cin >> a >> b;
    if (b == 0)
    {
        cout << '0';
        return 0;
    }
    vector<int> x;
    for (int i = a.size() - 1; i >= 0; i -- ) x.push_back(a[i] - '0');
    vector<int> res = mul(x, b);
    
    for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
    
    return 0;
}

点击并拖拽以移动

C语言： 

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
#include <stdio.h>
#include <math.h>
#include <string.h>

#define N 100010

char a[N];
int x[N], b;
int l;
int ans[N];

int fuc(int x[], int b)
{
    int t = 0; //进位
    for (int i = 0; i < l; i ++)
    {
        int sum =  x[i] * b + t;
        ans[i] = sum % 10;
        t = sum / 10;
    }
    
    return t;
}
int main()
{
    scanf("%s%d", a, &b);
    
    l = strlen(a);
    for (int i = l - 1, t = 0; i >= 0; i --) x[t ++] = a[i] - '0';
    
    if (b == 0 || (l == 1 && x[0] == 0)) 
    {
        printf("0\n");
        return 0;
    }
    int t = fuc(x, b);
    if (t) printf("%d", t);
    for (int i = l - 1; i >= 0; i --)
    {
        printf("%d", ans[i]);
    }   
    printf("\n");
    
    return 0;
}

点击并拖拽以移动

除法：

核心思想：

​ 1.规模大的数字按照字符串读入

​ 2.将字符串转化为数组

​ 3.将数组中的每一个数与数字相除

​ 4.去除前导0

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int t;
vector<int> divide(vector<int> x, int b)
{
    vector<int> res;
    
    for (int i = 0; i < x.size(); i ++ )
    {
        t = t * 10 + x[i];
        res.push_back(t / b);
        t = t % b;
    }
    reverse(res.begin(), res.end());
    
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    
    return res;
}

点击并拖拽以移动

高精度除法例题：

Acwing794.高精度除法

img点击并拖拽以移动

C++： 

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int t;
vector<int> divide(vector<int> x, int b)
{
    vector<int> res;
    
    for (int i = 0; i < x.size(); i ++ )
    {
        t = t * 10 + x[i];
        res.push_back(t / b);
        t = t % b;
    }
    reverse(res.begin(), res.end());
    
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    
    return res;
}
int main()
{
    string a;
    int b;
    cin >> a >> b;
    
    vector<int> x;
    for (int i = a.size() - 1; i >= 0; i -- ) x.push_back(a[i] - '0');
    reverse(x.begin(), x.end());
    vector<int> res = divide(x, b);
    for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
    cout << endl;
    cout << t << endl;
}

点击并拖拽以移动

C语言： 

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
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

#define N 100010

char a[N];
int x[N], b;
int l;
int ans[N];
int tmp[N];

bool cmp(int x[], int b)
{
    int cnt = 0;
    int t = b;
    while (t)
    {
        tmp[cnt ++] = t % 10;
        t /= 10;
    }
    
    if (cnt > l) return true;
    else if (cnt < l) return false;
    else
    {
        for (int i = cnt - 1, j = 0; i >= 0; i --, j ++)
        {
            if (tmp[i] > x[j]) return true;
            else return false;
        }
    }
}
int fuc(int x[], int b)
{
    int t = 0;
    for (int i = 0; i < l; i ++)
    {
        int sum = x[i] + t * 10;
        ans[i] = sum / b;
        t = sum % b;
    }
    return t;
}
int main()
{
    scanf("%s%d", a, &b);
    
    l = strlen(a);
    for (int i = 0; i < l; i ++) x[i] = a[i] - '0';
        
    int t = fuc(x, b);
    // b > a
    if (cmp(x, b)) printf("0\n");
    else 
    {
        int flag = true;
        for (int i = 0; i < l; i ++)
        {
            if (ans[i] != 0) flag = false;
            if (flag) continue;
            else printf("%d", ans[i]);
        }
        printf("\n");
    }
    printf("%d\n", t);
    return 0;
}

点击并拖拽以移动

前缀和与差分

一维前缀和：

图解分析：

img点击并拖拽以移动

模板：

1
2
3
4
5
6
7
8
9
10
int n, m;
int sum[N];
void Prefix_and(int a[])
{
    for (int i = 1; i <= n; i ++ )  sum[i] = sum[i - 1] + a[i];
}
int Sum(int l, int r)
{
    return sum[r] - sum[l - 1];
}

点击并拖拽以移动

一维前缀和例题（C++版）：

Acwing795.前缀和

img点击并拖拽以移动 

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
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int sum[N];
void Prefix_and(int a[])
{
    for (int i = 1; i <= n; i ++ )  sum[i] = sum[i - 1] + a[i];
}
int Sum(int l, int r)
{
    return sum[r] - sum[l - 1];
}
int main()
{
    cin >> n >> m;
   
    int a[N];
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    Prefix_and(a);
    while (m --)
    {
        int l, r;
        cin >> l >> r;
        cout << Sum(l, r) << endl;;
    }
}

点击并拖拽以移动

二维前缀和：

图解分析：

img点击并拖拽以移动

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
int n, m;
int sum[N][N];
void Prefix_and(int a[N][N])
{
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
int Sum(int x1, int y1, int x2, int y2)
{
    int res = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
    return res;
}

点击并拖拽以移动

二维前缀和例题（C++版）：

Acwing796.子矩阵的和

img点击并拖拽以移动 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
int sum[N][N];
void Prefix_and(int a[N][N])
{
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
int Sum(int x1, int y1, int x2, int y2)
{
    int res = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
    return res;
}
int main()
{
    int q;
    cin >> n >> m >> q;
    
    int a[N][N];
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ )
            cin >> a[i][j];
    Prefix_and(a);
    while (q --)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        cout << Sum(x1, y1, x2, y2) << endl;
    }
}

点击并拖拽以移动

一维差分：

图解分析：

对于差分数组b，可以看作b求前缀和就等于a

对于给定区间[l, r]， 每一个数都加上c：

​ b[l] + c 可以使得 a[l ~ n]的每一个数都加上c

​ b[r + 1] - c 可以使得 a[r + 1 ~ n] 的每一个数都减上c

img点击并拖拽以移动

模板：

1
2
3
4
5
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

点击并拖拽以移动

一维差分例题（C++版）：

img点击并拖拽以移动 

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
#include <iostream>

using namespace std;

const int N = 100010;
int a[N], b[N];
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}
int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);
     
    while (m --)
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }
    
    for (int i = 1 ; i <= n; i ++ ) 
    {
        b[i] += b[i - 1];
        cout << b[i] << ' ';
    }
}

点击并拖拽以移动

二维差分：

图解分析：

img点击并拖拽以移动

模板：

1
2
3
4
5
6
7
8
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

点击并拖拽以移动

二维差分例题（C++版）：

Acwing798.差分矩阵

img点击并拖拽以移动 

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
#include <iostream>

using namespace std;

const int N = 1010;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main()
{
    int n, m, q;
    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]);
            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] + b[i][j];
    
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            printf("%d ", b[i][j]);
        }
        puts("");
    }
}

点击并拖拽以移动

双指针算法

核心思想：

img点击并拖拽以移动

模板：

​ 双指针是一种思想，没有具体模板

双指针算法例题（C++版）：

Acwing799.最长连续不重复子序列

img点击并拖拽以移动

分析：

img点击并拖拽以移动

代码：

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int s[N];
int main()
{
    int n;
    scanf("%d", &n);
    
    int a[N];
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    int res = 0;
    int j = 0;
    for (int i = 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;
}

点击并拖拽以移动

Acwing800.数组元素的目标和

img点击并拖拽以移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
typedef long long LL;

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    
    LL a[N], b[N];
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < m; i ++ ) cin >> b[i];
    
    int j = m - 1;
    for (int i = 0; i < n; i ++ )
    {
        while (j >= 0 && a[i] + b[j] > x) j --;
        if (a[i] + b[j] == x) cout << i << ' ' << j << endl;
    }
}

点击并拖拽以移动

Acwing2816.判断子序列

img点击并拖拽以移动 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int main()
{
    int n, m;
    cin >> n >> m;
    
    int a[N], b[N];
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < m; i ++ ) cin >> b[i];
    
    int i = 0, j = 0;
    while (i < n && j < m)
    {
        if (a[i] == b[j]) i ++;
        j ++;
    }
    if (i == n) puts("Yes");
    else puts("No");
}

点击并拖拽以移动

位运算

位运算的基本知识：

img点击并拖拽以移动

位运算常用操作：

1.求x的第k位数字：

1
x >> k & 1;

点击并拖拽以移动

2.返回x的最后一位1:

1
lowbit(x) = x & -x;

点击并拖拽以移动

位运算例题（C++版）：

Acwing801.二进制中1的个数

img点击并拖拽以移动 

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
#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 cnt = 0;
        while (x)
        {
            x -= lowbit(x);
            cnt ++;
        }
        cout << cnt << ' ';
    }
}

点击并拖拽以移动

离散化

运用离散化的题目特点：

​ 值域大，个数少。

核心思路：

​ 1.用可变数组存储所有的下标，按大小排序后去重

​ 2.用二分查找的方法，查找出离散后的坐标，构造离散化以后的数组

去重模板（C++）：

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

点击并拖拽以移动

二分查找模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> alls;
int find(int x)
{
    int l = 0, r = alls.size();
    
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    
    return l + 1;
}

点击并拖拽以移动

离散化例题（C++版）：

Acwing802.区间和

img点击并拖拽以移动 

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
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 300010;
typedef pair<int, int> PII;

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();
    
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    
    return l + 1;
}
int main()
{
    cin >> n >> m;
    while (n --)
    {
        int x, c;
        cin >> x >> c;
        alls.push_back(x);
        
        add.push_back({x, c});
    }
    
    while (m --)
    {
        int l, r;
        cin >> l >> r;
        alls.push_back(l);
        alls.push_back(r);
        
        query.push_back({l, r});
    }
    //去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    
    for(auto item: add)
    {
        int k = find(item.first);
        a[k] = 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), r = find(item.second);
        
        cout << s[r] - s[l - 1] << endl;
    }
}

点击并拖拽以移动

区间合并

图解分析：

img点击并拖拽以移动

模板（C++）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<PII> segs, res;
void merge(vector<PII> segs)
{
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    
    for(auto item : segs)
    {
        if (ed < item.first)
        {
            if (ed != -2e9) res.push_back({st, ed});
            st = item.first;
            ed = item.second;
        }
        else ed = max(ed, item.second);
    }
    if (st != -2e9) res.push_back({st, ed});
}

点击并拖拽以移动

区间合并例题（C++版）：

Acwing803.区间合并

img点击并拖拽以移动 

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
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

vector<PII> segs, res;
void merge(vector<PII> segs)
{
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    
    for(auto item : segs)
    {
        if (ed < item.first)
        {
            if (ed != -2e9) res.push_back({st, ed});
            st = item.first;
            ed = item.second;
        }
        else ed = max(ed, item.second);
    }
    if (st != -2e9) res.push_back({st, ed});
}
int main()
{
    int n;
    cin >> n;
    
    while (n --)
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    merge(segs);
    cout << res.size() << endl;
}

点击并拖拽以移动

如有错误，欢迎指正！！！

所有笔记总结目录-CSDN博客