C++算法之旅、04 基础篇 | 第一章

常用代码模板1——基础算法 - AcWing
ios::sync_with_stdio(false)

提高 cin 读取速度，副作用是不能使用 scanf
数据输入规模大于一百万建议用scanf

快速排序

基于分治 nlog(n) (期望值)

• 确定分界点
  q[L]、q[ (L+R) / 2 ]、q[R]、随机点
  
• 调整区间 最难部分
  所有  = x 的元素在 x 右半边
  暴力做法： 开两个数组 a, b，遍历 q，如果  x 的元素放 b。把 a、b 的元素分别放入 q 里面去，q 相当于 a + x + b 。扫了两遍 O(n)
  优美方法： 开两个指针 a, b, 同时往中间走，a 先走，直到元素 >= x，i 停下来。移动 j，直到元素 < x，此时两个指针对应元素互换，各自移动一位
  
• 递归处理左右两段
  

785 ⭐

785. 快速排序 - AcWing题库
读入大量数据时，scanf更快一些。
另外本题有特殊情况，该情况下每次取区间起点或者终点作为分界点，则会超时。分界点换成随机值，或者区间中点即可。

1. #include <algorithm>
2. #include <cstdio>
4. using namespace std;
6. const int N = 1e6 + 10;
8. int n;
9. int q[N];
11. void quick_sort(int q[], int l, int r) {
12.     if (l >= r) return;
13.     int x = q[l + r >> 1], i = l - 1, j = r + 1;
14.     while (i < j) {
15.         do i++;
16.         while (q[i] < x);
17.         do j--;
18.         while (q[j] > x);
19.         if (i < j) swap(q[i], q[j]);
20.     }
21.     quick_sort(q, l, j), quick_sort(q, j + 1, r);
22.     // ^ 在[1,2]数组情况下x不能取右边界点，否则会陷入死循环
23.     // quick_sort(q, l, i-1), quick_sort(q, i, r);
24.     // ^ 在[1,2]数组情况下x不能取左边界点，否则会陷入死循环
25. }
27. int main() {
28.     scanf("%d", &n);
29.     for (int i = 0; i < n; i++) scanf("%d", &q[i]);
30.     quick_sort(q, 0, n - 1);
31.     for (int i = 0; i < n; i++) printf("%d ", q[i]);
33.     return 0;
34. }

复制代码

786

786. 第k个数 - AcWing题库

1. #include <algorithm>
2. #include <cstdio>
3. #include <iostream>
5. using namespace std;
7. const int N = 1e5 + 10;
8. int q[N];
10. void quick_sort(int q[], int l, int r) {
11.     if (l >= r) return;
12.     int x = q[l + r >> 1], i = l - 1, j = r + 1;
13.     while (i < j) {
14.         do i++;
15.         while (q[i] < x);
16.         do j--;
17.         while (q[j] > x);
18.         if (i < j) swap(q[i], q[j]);
19.     }
20.     quick_sort(q, l, j);
21.     quick_sort(q, j + 1, r);
22. }
24. int main() {
25.     int n, k;
26.     cin >> n >> k;
27.     for (int i = 0; i < n; i++) {
28.         scanf("%d", &q[i]);
29.     }
30.     quick_sort(q, 0, n - 1);
31.     printf("%d", q[k - 1]);
33.     return 0;
34. }

复制代码

归并排序

基于分治 nlog(n)

• 找分界点，mid = (l+r) / 2（归并是找下标，快排是找数）
  
• 递归排序left，right
  
• 归并，把两个有序数组合二为一，使用双指针法。O(n)，需要额外辅助数组
  

排序算法的稳定与否，就是排序过程中数组中两个相等的数据，经过排序后，排序算法能保证其相对位置不发生变化，是稳定排序算法。归并过程中发现两个相同元素优先放入第一个指针的元素

787 ⭐

787. 归并排序 - AcWing题库

1. #include <cstdio>
2. #include <iostream>
4. using namespace std;
6. const int N = 1e6 + 10;
8. int n;
9. int q[N], tmp[N];
11. void merge_sort(int q[], int l, int r) {
12.     if (l >= r) return;
13.     int mid = l + r >> 1;
14.     merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
15.     int i = l, j = mid + 1, k = 0;
16.     while (i <= mid && j <= r) {
17.         if (q[i] <= q[j])
18.             tmp[k++] = q[i++];
19.         else
20.             tmp[k++] = q[j++];
21.     }
22.     while (i <= mid) tmp[k++] = q[i++];
23.     while (j <= r) tmp[k++] = q[j++];
24.     for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
25. }
27. int main() {
28.     int n;
29.     cin >> n;
30.     for (int i = 0; i < n; i++) {
31.         scanf("%d", &q[i]);
32.     }
33.     merge_sort(q, 0, n - 1);
34.     for (int i = 0; i < n; i++) {
35.         printf("%d ", q[i]);
36.     }
37.     return 0;
38. }

复制代码

ANTI WEB SPIDER BOT www.cnblogs.com/linxiaoxu
高精度（整数运算）


大整数位数  1e6 ，小整数值 > a >> b;    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a - '0');    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b - '0');    auto C = add(A, B);    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C);    return 0;}[/code]
A - B

792. 高精度减法 - AcWing题库
要保证 A >= B，如果B大，则算 -(B - A) ；如果 A、B 有负数，可以转换成 |A| - |B| 或 |A| + |B|。

1. #include <cstdio>
2. #include <iostream>
4. using namespace std;
6. typedef long long LL;
8. const int N = 1e6 + 10;
10. int n;
11. int q[N], tmp[N];
13. LL merge_sort_count(int q[], int l, int r) {
14.     if (l >= r) return 0;
15.     int mid = l + r >> 1;
16.     int k = 0, i = l, j = mid + 1;
17.     LL count = merge_sort_count(q, l, mid) + merge_sort_count(q, mid + 1, r);
18.     while (i <= mid && j <= r) {
19.         if (q[i] <= q[j])
20.             tmp[k++] = q[i++];
21.         else {
22.             count += mid - i + 1;
23.             tmp[k++] = q[j++];
24.         }
25.     }
26.     while (i <= mid) tmp[k++] = q[i++];
27.     while (j <= r) tmp[k++] = q[j++];
28.     for (int i = l, k = 0; i <= r; i++, k++) q[i] = tmp[k];
29.     return count;
30. }
32. int main() {
33.     int n;
34.     cin >> n;
35.     for (int i = 0; i < n; i++) {
36.         scanf("%d", &q[i]);
37.     }
39.     cout << merge_sort_count(q, 0, n - 1);
41.     return 0;
42. }

复制代码

A *  b

793. 高精度乘法 - AcWing题库
把 b 看成一个整体去和 A 一位一位乘；记得处理b为0时的特殊情况、还有高位进位

1. #include <cstdio>
2. #include <iostream>
4. using namespace std;
6. typedef long long LL;
8. const int N = 1e6 + 10;
10. int q[N];
12. int main() {
13.     int n, m;
14.     cin >> n >> m;
15.     for (int i = 0; i < n; i++) {
16.         scanf("%d", &q[i]);
17.     }
18.     while (m--) {
19.         int k;
20.         cin >> k;
21.         // ^ 寻找右区间边界点
22.         int l = 0, r = n - 1;
23.         while (l < r) {
24.             int mid = l + r >> 1;
25.             if (q[mid] >= k)
26.                 r = mid;
27.             else
28.                 l = mid + 1;
29.         }
30.         if (q[l] != k) {
31.             cout << "-1 -1" << endl;
32.             continue;
33.         } else
34.             cout << l << " ";
35.         l = 0, r = n - 1;
36.         while (l < r) {
37.             int mid = l + r + 1 >> 1;
38.             if (q[mid] <= k)
39.                 l = mid;
40.             else
41.                 r = mid - 1;
42.         }
43.         cout << r << endl;
44.     }
45.     return 0;
46. }

复制代码

返回最后一位1 lowbit

1. // while(r-l >= 1e-8)
2. for (int i = 0; i < 100; i++) {
3.     double mid = (l + r) / 2;
4.     if (mid * mid * mid >= x)
5.         r = mid;
6.     else
7.         l = mid;
8. }

复制代码

801

801. 二进制中1的个数 - AcWing题库

1. #include <cstdio>
2. #include <iostream>
4. using namespace std;
6. int main() {
7.     double x;
8.     cin >> x;
9.     double l = 0, r = x;
10.     if (x < -1)  // 负数时调换两者位置
11.         l = x, r = 0;
12.     else if (x > -1 && x < 1)  // 小数时范围是 [-1,1]
13.         l = -1, r = 1;
15.     // while(r-l >= 1e-8)
16.     for (int i = 0; i < 100; i++) { // 区间长度 / (1 << 100)
17.         double mid = (l + r) / 2;
18.         if (mid * mid * mid >= x)
19.             r = mid;
20.         else
21.             l = mid;
22.     }
23.     printf("%lf\n", l);
24.     return 0;
25. }

复制代码

802

802. 区间和 - AcWing题库
当数组下标小的时候可以用前缀和做，该题区间范围2e9（跨度大），但稀疏（元素少），可以先整数离散化，然后再前缀和
数组开30万(n+2m)，插入10万，查询20万
[code]#include #include #include #include using namespace std;typedef pair PII;const int N = 3e5 + 10;// 差分int s[N];vector alls;vector 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() {    int n, m;    cin >> n >> m;    while (n--) {        int x, c;        cin >> x >> c;        add.push_back({x, c});        alls.push_back(x);    }    for (int i = 0; i < m; i++) {        int l, r;        cin >> l >> r;        query.push_back({l, r});        alls.push_back(l);        alls.push_back(r);    }    // 去重    sort(alls.begin(), alls.end());    alls.erase(unique(alls.begin(), alls.end()), alls.end());    // 插入    for (auto item : add) {        int x = find(item.first);        s[x] += item.second;    }    // 差分转前缀和    for (int i = 1; i > l >> r;        a.push_back({l, r});    }    auto res = merge(a);    cout  n;    // 步骤1 输入    while (n--) {        int x1, y1, x2, y2;        cin >> x1 >> y1 >> x2 >> y2;        if (x1 == x2) {            rows.push_back({x1, min(y1, y2), max(y1, y2)});        } else {            cols.push_back({y1, min(x1, x2), max(x1, x2)});        }    }    sort(rows.begin(), rows.end());    sort(cols.begin(), cols.end());    // 步骤2 合并区间    rows = merge(rows);    cols = merge(cols);    // 步骤3 计算    long long res = 0;  // 最大值可以是 (2e9)平方=4e18    for (int i = 0; i < rows.size(); i++) {        res += rows.r - rows.l + 1;    }    for (int i = 0; i < cols.size(); i++) {        res += cols.r - cols.l + 1;    }    // 步骤4 去重    for (int i = 0; i < rows.size(); i++) {        for (int j = 0; j < cols.size(); j++) {            auto row = rows;            auto col = cols[j];            if (row.l = col.no && col.l = row.no)                res--;        }    }    cout