标签：int 基础 back 第一章 ++ 算法 vector include size

1 快速排序算法
- 1.2 第 k 个数
2 归并排序算法
- 2.2 逆序对数量
3 二分
- 3.1 数的范围
- 3.2 数的三次方根
4 高精度算法
5 前缀和与差分
6 双指针算法
7 位运算
- 7.1 二进制中 1 的个数
8 离散化
9 区间合并

1 快速排序算法

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, a[N];

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

1.2 第 k 个数

Acwing 786

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, k, a[N];

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

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    int ret = quick_sort(a, 0, n - 1, k);
    printf("%d\n", ret);
    return 0;
}

2 归并排序算法

Acwing 787

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, nums[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;
    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() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", nums + i);
    merge_sort(nums, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", nums[i]);
    puts("");
    return 0;
}

2.2 逆序对数量

Acwing 788

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

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 i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) 
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else {
            res += mid - i + 1;
            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];
    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> q[i];
    cout << merge_sort(0, n - 1) << endl;
    return 0;
}

3 二分

3.1 数的范围

Acwing 789

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, m, q[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", q + i);
    while (m--) {
        int x; scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r) { // 查找起始位置
            int mid = (l + r) >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (q[l] != x) {
            printf("-1 -1\n");
            continue;
        }
        printf("%d ", l);
        l = 0, r = n - 1;
        while (l < r) { // 查找终止位置
            int mid = (l + r + 1) >> 1;
            if (q[mid] <= x) l = mid;
            else r = mid - 1;
        }
        printf("%d\n", l);
    }
    return 0;
}

3.2 数的三次方根

Acwing 790

按照经验，计算结果的精度要比题目要求的精度高两位。

#include <iostream>
using namespace std;

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

4 高精度算法

4.1 加法

Acwing 791

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

int main() {
    string a, b; cin >> a >> b;
    vector<int> 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');
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    cout << endl;
    return 0;
}

4.2 减法

Acwing 792

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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;
    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);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && !C.back()) C.pop_back();
    return C;
}

int main() {
    string a, b; cin >> a >> b;
    vector<int> 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');
    vector<int> C;
    if (cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    cout << endl;
    return 0;
}

4.3 乘法

Acwing 793

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    for (int i = 0, t = 0; i < A.size() || t; i++) { // 这里的t是用来处理最后算完后依然会有进位的情况！
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && !C.back()) C.pop_back();
    return C;
}

int main() {
    string a; int b; cin >> a >> b;
    vector<int> A;
    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];
    cout << endl;
    return 0;
}

4.4 除法

Acwing 794

#include <iostream>
#include <algorithm>
#include <vector>
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() > 1 && !C.back()) C.pop_back();
    return C;
}

int main() {
    string a; int B; cin >> a >> B;
    vector<int> A;
    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 << endl;
    return 0;
}

5 前缀和与差分

5.1 一维前缀和

Acwing 795

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n, m, s[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        s[i] += s[i - 1] + x;
    }
    while (m--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

5.2 二维前缀和

Acwing 796

#include <iostream>
using namespace std;

const int N = 1010;

int n, m, q;
int 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++) {
            int x; scanf("%d", &x);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
        }
    while (q--) {
        int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}

5.3 一维差分

Acwing 797

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n, m, b[N];

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

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        insert(i, i, x);
    }
    while (m--) {
        int l, r, c; scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
        printf("%d ", b[i]);
    }
    return 0;
}

5.4 二维差分

Acwing 798

#include <iostream>
using namespace std;

const int N = 1010;

int n, m, q, x, b[N][N];

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

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &x);
            insert(i, j, i, j, x);
        }
    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];
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }
    return 0;
}

6 双指针算法

6.1 最长连续不重复子序列

Acwing 799

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n;
int q[N], s[N]; // q存储元素，s记录元素q[i]出现次数

int main() {
    scanf("%d", &n);
    int res = 0;
    for (int i = 0, j = 0; i < n; i++) {
        scanf("%d", q + i);
        s[q[i]]++;
        while (s[q[i]] > 1) s[q[j++]]--;
        res = max(res, i - j + 1);
    }
    printf("%d\n", res);
    return 0;
}

6.2 数组元素的目标和

Acwing 800

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, m, x;
int a[N], b[N];

int main() {
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 0; i < m; i++) scanf("%d", b + i);
    for (int i = 0, j = m - 1; i < n; i++) {
        while (j >= 0 && a[i] + b[j] > x) j--;
        if (j >= 0 && a[i] + b[j] == x) printf("%d %d\n", i, j);
    }
    return 0;
}

6.3 判断子序列

Acwing 2816

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

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

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 0; i < m; i++) scanf("%d", 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");
    return 0;
}

7 位运算

7.1 二进制中 1 的个数

Acwing 801

// 解法一
int judge(int x) {
    int ret = 0;
    while (x) {
        x &= (x - 1); // 去掉x最右边的一个 1
        ret++;
    }
    return ret;
}

// 解法二
int judge(int x) {
    int ret = 0;
    for (int i = x; i; i -= i & -i) ret++; // 每一次循环减去 n 的最后一位 1
    return ret;
}

8 离散化

Acwing 802

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
const int N = 3e5 + 10;

int n, m;
int 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 r + 1; // 注意下标
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        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 <= alls.size(); i++) s[i] += s[i - 1];
    for (auto item: query) {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

9 区间合并

Acwing 803

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

int n;
vector<PII> segs;

void merge(vector<PII> &segs) {
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for (auto seg: segs) 
        if (ed < seg.x) {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.x, ed = seg.y;
        } else ed = max(ed, seg.y);
    if (st != -2e9) res.push_back({st, ed});
    segs = res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r; cin >> l >> r;
        segs.push_back({l, r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}

标签：int,基础,back,第一章,++,算法,vector,include,size
From： https://www.cnblogs.com/lumoumou/p/17066687.html

第一章基础算法

1 快速排序算法

1.2 第 k 个数

2 归并排序算法

2.2 逆序对数量

3 二分

3.1 数的范围

3.2 数的三次方根

4 高精度算法

4.1 加法

4.2 减法

4.3 乘法

4.4 除法

5 前缀和与差分

5.1 一维前缀和

5.2 二维前缀和

5.3 一维差分

5.4 二维差分

6 双指针算法

6.1 最长连续不重复子序列

6.2 数组元素的目标和

6.3 判断子序列

7 位运算

7.1 二进制中 1 的个数

8 离散化

9 区间合并

相关文章

赞助商

阅读排行

第一章 基础算法

1 快速排序算法

1.2 第 k 个数

2 归并排序算法

2.2 逆序对数量

3 二分

3.1 数的范围

3.2 数的三次方根

4 高精度算法

4.1 加法

4.2 减法

4.3 乘法

4.4 除法

5 前缀和与差分

5.1 一维前缀和

5.2 二维前缀和

5.3 一维差分

5.4 二维差分

6 双指针算法

6.1 最长连续不重复子序列

6.2 数组元素的目标和

6.3 判断子序列

7 位运算

7.1 二进制中 1 的个数

8 离散化

9 区间合并

相关文章

赞助商

阅读排行

第一章基础算法