排序

快速排序

快排的核心思想：分治，平均时间复杂度是O(nlogn)

设一整行的数，左边是l、右边是r：

  1. 确定分界点：取一个点x，可以是左边界q[l]、中点q[(l+r)/2]、右边界q[r]。
  2. 调整区间：小于等于x的放在左边，大于等于的在右边。
  3. 递归处理左右两段。

关于如何调整区间可以使用如下“暴力”方法：

  1. 开两个额外数组a[]，b[]
  2. 扫描q[l] ~ q[r]每一个数 q[i]，如果q[i]小于等于x，则插入到a[]中，否则放到b[]中
  3. 先把a[]放到q[]中，再把b[]放到q[]中

正常使用双指针：

  1. 初始化两个指针i、j分别指向左边界q[l]和右边界q[r]
  2. 将q[i]与x相比，若q[i]小于等于x，则将指针右移；若q[i]大于x，则将q[j]于x相比,若q[j]大于等于x，则将指针左移，直到q[i]大于x且q[j]小于x
  3. 交换此时的q[i]与q[j]
  4. 递归处理

快排实现

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

using namespace std;

const int N = 1000000;

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;                             //若无数据则直接返回不进行排序

    int x = q[l], i = l - 1, j = r + 1;             //定义x为左边界值与双指针，因为每次循环需要先移动指针所以指针的初始位置应该在左右边界的外侧
    
    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);                        //需要注意如果取的边界值是左边q[l]，则对两侧排序需要用到j与j+1，否则会出现边界问题；如果取的是右边q[r]，则应该使用i-1与i
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++)
        cin >> q[i];
    
    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++)
        cout << q[i] << ' ';

    return 0;
}

快排模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int x = q[l], 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);
}

归并排序

归并排序的核心思想：分治，时间复杂度为O(nlogn)

归并排序步骤

  1. 将整个序列从中间分成左右两边：mid = (l + r) >>
  2. 递归排序left、right
  3. 归并左右两个序列合二为一（双指针）

Step3

  1. 两个指针分别指向左右两个序列的最小值，比较后更小的就是整个序列的最小值
  2. 再将较小值所在的序列上的指针向后移动，并不断比较，直到一个序列指针走到终点
  3. 另一个序列上后面的数依次放在后面

归并排序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>

using namespace std;

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

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;                                             //若无数据则直接返回不进行排序
    
    int mid = (l + r) >> 1;                              //取当前序列的中点

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);   //递归排序左右两边

    int k = 0, i = l, j = mid + 1;                      //定义k作为临时存储数组的计数器，定义双指针

    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 = l, j = 0; i <= r; i ++, j ++)          //将临时数组tmp[]中的元素放回q[]中
        q[i] = tmp[j];
}

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

    merge_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++)
        cout << 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
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    
    int mid = (l + r) >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;

    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j])
            tmp[k ++] = q[i ++];
        else
            tmp[k ++] = q[j ++];
    }

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

    for (int i = l, j = 0; i <= r; i ++, j ++)
        q[i] = tmp[j];
}

快速排序与归并排序对比

  1. 时间复杂度：快速排序与归并排序的时间复杂度都是O(nlogn)。但快速排序的时间复杂度是一个期望值，在最差情况下会达到O(n^2)；而归并排序一直都是O(nlogn)。
  2. 空间复杂度：归并排序因为要开新序列，占用空间，其空间复杂度为O(n)；快排的时间复杂度为O(1)。
  3. 稳定性：归并排序的稳定性更高。
  4. 局部有序性：快速排序是先整体有序，然后局部有序；归并排序是先局部有序，然后整体有序。

二分查找

整数二分

整数二分的本质：整个区间被一分为二，左边不满足所给性质，右边满足所给性质，二分就可以寻找性质的边界。

与单调性的关系：如果有单调性则一定可以二分，但可以二分不一定非要有单调性。

整数二分（一）：找左侧条件的右边界点

步骤

  1. 找中间值mid = (l + r) + 1 >> 1
  2. 判断中间值是否满足条件：if (check (mid))
  3. 若check成立，说明此时的mid满足所给条件，则要找的边界在[mid, r]区间内，更新区间l = mid
  4. 若check不成立，则说明此时的mid不满足所给条件，则要找的边界在[l, mid - 1]区间内，更新区间r = mid - 1

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool check(int x) {}

int bsearch(int l, int r)
{
    while(l < r)
    {
        int mid = l + r + 1 >> 1;

        if (check(mid))
            l = mid;
        else r = mid - 1;
    }
    return l;
}

整数二分（二）：找右侧条件的左边界点

步骤

  1. 找中间值mid = (l + r) >> 1
  2. 判断中间值是否满足条件：if (check (mid))
  3. 若check成立，说明此时的mid满足所给条件，则要找的边界在[l, mid]区间内，更新区间r = mid
  4. 若check不成立，则说明此时的mid不满足所给条件，则要找的边界在[mid + 1, r]区间内，更新区间l = mid + 1

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool check(int x) {}

int bsearch(int l, int r)
{
    while(l < r)
    {
        int mid = l + r >> 1;

        if (check(mid))
            r = mid;
        else l = mid + 1;
    }
    return l;
}

浮点数二分

例：求平方根，误差小于10^-6

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

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = 0, r = max(1, x);
    while (r - l > 1e-6)                    //若要求保留四位小数，使用1e-6，五位小数使用1e-7，六位使用1e-8
    {
        double mid = (l + r) / 2;

        if (mid * mid >= x)
            r = mid;
        else
            l = mid;
    }

    cout << l << endl;
    return 0;
}

习题

  1. 快速排序

    给定你一个长度为n的整数数列。

    请你使用快速排序对这个数列按照从小到大进行排序。

    并将排好序的数列按顺序输出。

    输入格式

    输入共两行，第一行包含整数n。

    第二行包含n个整数（所有整数均在 1∼10^6范围内），表示整个数列。

    输出格式

    输出共一行，包含n个整数，表示排好序的数列。

    数据范围

    1≤n≤100000

    输入样例

    1
    2
    5
    3 1 2 4 5

    输出样例

    1
    1 2 3 4 5

    解

    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
    //x定为左端点
    #include <iostream>

    using namespace std;

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

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

        int x = q[l], 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()
    {
        cin >> n;

        for (int i = 0; i < n; i ++)
            cin >> q[i];

        quick_sort(q, 0, n - 1);

        for (int i = 0; i < n; i ++)
            cout << 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
    41
    42
    43
    44
    45
    46
    //将x定为序列内随机位置，可能使快速排序时间复杂度降低
    #include <iostream>
    #include <time.h>

    using namespace std;

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

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

        int random_index = rand()%(r - l + 1) + l;  //在[l, r]区间定义随机索引，并将[0, r - l]内的随机索引平移到[l, r]中
        swap(q[random_index], q[l]);
        
        int x = q[l], 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()
    {
        srand(time(nullptr));                       //设置随机数种子
        cin >> n;

        for (int i = 0; i < n; i ++)
            cin >> q[i];

        quick_sort(q, 0, n - 1);

        for (int i = 0; i < n; i ++)
            cout << q[i] << ' ';

        return 0;
    }

  2. 第k个数

    给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列从小到大排序后的第k个数。

    输入格式

    第一行包含两个整数n和k。

    第二行包含n个整数（所有整数均在1∼10^9范围内），表示整数数列。

    输出格式

    输出一个整数，表示数列的第k小数

    数据范围

    1≤n≤100000

    1≤k≤n

    输入样例

    1
    2
    5 3
    2 4 1 5 3

    输出样例

    1
    3

    解

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

    using namespace std;

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

    int quick_sort(int l, int r, int k)
    {
        if (l >= r) return q[l];
        int x = q[l], 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]);
        }
        int sl = j - l + 1;
        if (k <= sl)    return quick_sort(l, j, k);
        return quick_sort(j + 1, r, k - sl);
    }

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

        for (int i = 0; i < n; i ++)    cin >> q[i];

        cout << quick_sort(0, n - 1, k) << endl;

        return 0;
    }

  3. 归并排序

    给定你一个长度为n的整数数列。请你使用归并排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。

    输入格式

    第一行包含两个整数n和k。

    第二行包含n个整数（所有整数均在1∼10^9范围内），表示整数数列。

    输出格式

    输出共一行，包含n个整数，表示排好序的数列。

    数据范围

    1≤n≤100000

    1≤k≤n

    输入样例

    1
    2
    5
    3 1 2 4 5

    输出样例

    1
    1 2 3 4 5

    解

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

    using namespace std;

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

    void merge_sort(int q[], int l, int r)
    {
        if (l >= r) return;

        int mid = (l + r) >> 1;
        int k = 0, i = l, j = mid + 1;

        merge_sort(q, l, mid);
        merge_sort(q, mid + 1, r);

        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 = l, j = 0; i <= r; i ++, j ++)
            q[i] = tmp[j];
    }

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

        merge_sort(q, 0, n - 1);

        for (int i = 0; i < n; i ++)
            cout << q[i] << ' ';
        
        return 0;
    }

  4. 逆序对的数量

    给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

    输入格式

    第一行包含整数 n，表示数列的长度。第二行包含 n个整数，表示整个数列。

    输出格式

    输出一个整数，表示逆序对的个数

    数据范围

    1≤n≤100000

    数列中的元素的取值范围 [1,10^9]

    输入样例

    1
    2
    6
    2 3 4 5 6 1

    输出样例

    1
    5

    解

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

    using namespace std;

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

    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 k = 0, i = l, j = mid + 1;

        while (i <= mid && j <= r)                                      //归并并整理逆序对的过程
        {
            if (q[i] <= q[j])
                tmp[k ++] = q[i ++];
            else
            {
                tmp[k ++] = q[j ++];
                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;
    }

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

        cout << merge_sort(0, n - 1);

        return 0;
    }

  5. 数的范围

    给定一个按照升序排列的长度为n的整数数组，以及q个查询。

    对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

    如果数组中不存在该元素，则返回 -1 -1。

    输入格式

    第一行包含整数n和q，表示数组长度和询问个数。

    第二行包含n个整数（均在 1∼10000范围内），表示完整数组。

    接下来q行，每行包含一个整数k，表示一个询问元素。

    输出格式

    共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

    如果数组中不存在该元素，则返回 -1 -1。

    数据范围

    11≤n≤100000

    1≤q≤10000

    1≤k≤10000

    输入样例

    1
    2
    3
    4
    5
    6 3
    1 2 2 3 3 4
    3
    4
    5

    输出样例

    1
    2
    3
    3 4
    5 5
    -1 -1

    解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    #include <iostream>

    using namespace std;

    const int N = 100010;

    int main()
    {
        int n, q, a[N];
        cin >> n >> q;
        for (int i = 0; i < n; i ++)
            cin >> a[i];

        while(q --)
        {
            int x;
            cin >> x;

            int l = 0, r = n - 1;
            while(l < r)
            {
                int mid = l + r >> 1;

                if (a[mid] >= x)
                    r = mid;
                else
                    l = mid + 1;
            }
            
            if (a[l] != x)
                cout << "-1 -1" << endl;
            else
            {
                cout << l << ' ';

                int l = 0, r = n - 1;
                while(l < r)
                {
                    int mid = l + r + 1 >> 1;

                    if (a[mid] <= x)
                        l = mid;
                    else
                        r = mid - 1;
                }

                cout << l << endl;
            }
        }

        return 0;
    }

  6. 数的三次方根

    给定一个浮点数n，求它的三次方根。

    输入格式

    共一行，包含一个浮点数n

    输出格式

    共一行，包含一个浮点数，表示问题的解。

    注意，结果保留6位小数。

    数据范围

    −10000≤n≤10000

    输入样例

    1
    1000.00

    输出样例

    1
    10.000000

    解

    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;

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

        
        double l = -10000, r = 10000;
        while (r - l > 1e-8)
        {
            double mid = (l + r) / 2;

            if (mid * mid * mid >= n)
                r = mid;
            else
                l = mid;
        }

        printf("%.6lf", l);
        return 0;
    }

高精度

高精度加法

大整数存储

将较大的数的每一位分别存储到数组元素中，个位存到数组的第0个位置（便于进位），以此类推。

高精度运算实际上是模拟人工计算的过程

例题

  1. 高精度加法

    给定两个正整数（不含前导0），计算它们的和。

    输入格式

    共两行，每行包含一个整数。

    输出格式

    共一行，包含所求的和。

    数据范围

    1≤整数长度≤100000

    输入样例

    1
    2
    12
    23

    输出样例

    1
    35

    解

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

    using namespace std;

    const int N = 100010;

    vector<int> add(vector<int> &A, vector<int> &B)         //加引用提高效率
    {
        vector<int> C;
        int t = 0;                                          //设置进位                                     

        for (int i = 0; i < A.size()||i < B.size(); i ++)
        {
            if (i < A.size())
                t += A[i];
            if (i < B.size())
                t += B[i];
            
            C.push_back(t % 10);
            t /= 10;
        }

        if (t)
            C.push_back(1);

        return C;
    }

    int main()
    {
        string a, b;
        vector<int> A, B;

        cin >> a >> b;                                      //a = "123456"
        for (int i = a.size() - 1; i >= 0; i --)
            A.push_back(a[i] - '0');                        //A = [6, 5, 4, 3, 2, 1]
        
        for (int i = b.size() - 1; i >= 0; i --)
            B.push_back(b[i] - '0');

        vector<int> C = add(A, B);

        for (int i = C.size() - 1; i >= 0; i --)
            cout << C[i];

        return 0;
    }

  2. 高精度减法

    给定两个正整数（不含前导0），计算它们的差，计算结果可能为负数。

    输入格式

    共两行，每行包含一个整数。

    输出格式

    共一行，包含所求的和。

    数据范围

    1≤整数长度≤100000

    输入样例

    1
    2
    32
    11

    输出样例

    1
    21

    解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    #include <iostream>
    #include <vector>

    using namespace std;

    //判断是否有 A >= B
    bool cmp(vector<int> &A, vector<int> &B)
    {
        if (A.size() != B.size()) return A.size() > B.size();
        for (int i = A.size() - 1; i >= 0; i --)
            if (A[i] != B[i])
                return A[i] > B[i];
        return true;
    }

    vector<int> sub(vector<int> A, vector<int> B)
    {
        vector<int> C;
        int t = 0;

        for (int i = 0; i < A.size(); i ++)
        {
            t = A[i] - t;
            if (i < B.size()) t -= B[i];
            C.push_back((t + 10) % 10);
            if (t < 0) t = 1;
            else t = 0;
        }

        while (C.size() > 1 && C.back() == 0)
            C.pop_back();

        return C;
    }

    int main()
    {
        string a, b;
        vector<int> A, B;

        cin >> a >> b;

        for (int i = a.size() - 1; i >= 0; i --)
            A.push_back(a[i] - '0');
        for (int i = b.size() - 1; i >= 0; i --)
            B.push_back(b[i] - '0');
        
        if(cmp(A, B))
        {
            vector<int> C = sub(A, B);

            for (int i = C.size() - 1; i >= 0; i --)
                cout << C[i];
        }
        else
        {
            vector<int> C = sub(B, A);
            
            cout << '-';
            for (int i = C.size() - 1; i >= 0; i --)
                cout << C[i];
        }

        return 0;
    }

  3. 高精度乘法

    给定两个非负整数（不含前导0）A和B，请你计算 A×B的值。

    输入格式

    共两行，每行包含一个整数。

    输出格式

    共一行，包含所求的值。

    数据范围

    1≤A的长度≤100000,0≤B≤10000

    输入样例

    1
    2
    2
    3

    输出样例

    1
    6

    解

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

    using namespace std;

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

        for (int i = 0; i < A.size() || t; i ++)
        {
            if (i < A.size())
                t += A[i] * b;
            C.push_back(t % 10);
            t /= 10;
        }

        while (C.size() > 1 && C.back() == 0)
            C.pop_back();

        return C;
    }

    int main()
    {
        string a;
        int b;
        vector<int> A;

        cin >> a >> b;
        for (int i = a.size() - 1; i >= 0; i --)
            A.push_back(a[i] - '0');

        auto C = mul(A, b);

        for (int i = C.size() - 1; i >= 0; i --)
            cout << C[i];
        
        return 0;
    }

  4. 高精度除法

    给定两个非负整数（不含前导0）A和B，请你计算 A/B的商和余数。

    输入格式

    共两行，每行包含一个整数。

    输出格式

    共两行，第一行输出所求的商，第二行输出所求余数。

    数据范围

    1≤A的长度≤100000,0≤B≤10000，B一定不为0

    输入样例

    1
    2
    7
    2

    输出样例

    1
    2
    3
    1

    解

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

    using namespace std;

    vector<int> div(vector<int> &A, int b, int &r)
    {
        vector<int> C;
        r = 0;

        for (int i = A.size() - 1; i >= 0; i --)
        {
            r = r * 10 + A[i];
            C.push_back(r % b);
            r /= b;
        }

        reverse(C.begin(), C.end());

        while (C.size() > 0 && C.back() == 0)
            C.pop_back();

        return C;
    }

    int main()
    {
        string a;
        int b;
        vector<int> A;

        cin >> a >> b;
        for (int i = a.size() - 1; i >= 0; i --)
            A.push_back(a[i] - '0');

        int r;
        auto C = div(A, b, r);

        for (int i = C.size() - 1; i >= 0; i --)
            cout << C[i];
        cout << endl << r;

        return 0;
    }

  5. 前缀和

    输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l,r。

    对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

    输入格式

    第一行包含两个整数 n 和 m。

    第二行包含 n 个整数，表示整数数列。

    接下来 m 行，每行包含两个整数 l和 r，表示一个询问的区间范围。

    输出格式

    共 m 行，每行输出一个询问的结果。

    数据范围

    1≤l≤r≤n

    1≤n,m≤100000

    −1000≤数列中元素的值≤1000

    输入样例

    1
    2
    3
    4
    5
    5 3
    2 1 3 6 4
    1 2
    1 3
    2 4

    输出样例

    1
    2
    3
    3
    6
    10

    解

    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;

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

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

        while (m --)
        {
            int l, r;
            cin >> l >> r;
            cout << s[r] - s[l - 1] << endl;
        }

        return 0;
    }

  6. 子矩阵的和

    输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

    对于每个询问输出子矩阵中所有数的和。

    输入格式

    第一行包含三个整数 n，m，q。

    接下来n行，每行包含m个整数，表示整数矩阵。

    接下来q行，每行包含四个整数x1,y1,x2,y2，表示一组询问。

    输出格式

    共q行，每行输出一个询问的结果。

    数据范围

    1≤n,m≤1000

    1≤q≤200000

    1≤x1≤x2≤n

    1≤y1≤y2≤m

    −1000≤矩阵内元素的值≤1000

    输入样例

    1
    2
    3
    4
    5
    6
    7
    3 4 3
    1 7 2 4
    3 6 2 8
    2 1 2 3
    1 1 2 2
    2 1 3 4
    1 3 3 4

    输出样例

    1
    2
    3
    17
    27
    21

    解