模板-第一讲 基础算法

快速排序

时间复杂度O(nlogn)
这里涉及到很多边界处理的问题，所以直接记住下面这个模板。使用quick_sort(q, 0, n-1)；
实现从小到大排序。

void quick_sort(int q[], int l, int r){
    if(l >= r) return;
    int k = q[l + r >> 1];
    int i = l - 1, j = r + 1;
    while(i < j){
        do i++; while(q[i] < k);
        do j--; while(q[j] > k);
        if(i < j){
            int tmp = q[i];
            q[i] = q[j];
            q[j] = tmp;
        }
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

实现从大到小(只要改变与k比较的符号)

void quick_sort(int q[], int l, int r){
    if(l >= r) return;
    int k = q[l + r >> 1];
    int i = l - 1, j = r + 1;
    while(i < j){
        do i++; while(q[i] > k);
        do j--; while(q[j] < k);
        if(i < j){
            int tmp = q[i];
            q[i] = q[j];
            q[j] = tmp;
        }
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

归并排序

时间复杂度O(nlongn)

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

二分

时间复杂度O(logn)
整数
注意求mid时，l + r加不加1的问题。
加不加1完全取决于写的是l = mid，还是r = mid，和其他因素毫无关系。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, q;
int a[N];

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

    while(q--){
        scanf("%d", &k);

        int l = 0, r = n - 1;
        while(l < r){
            //注意这里mid不用+1再除以2
            int mid = (l + r) >> 1;
            if(a[mid] >= k) r = mid;
            else l = mid + 1;
        }

        if (a[l] != k) printf("%d %d\n", -1, -1);
        else{
            printf("%d ", l);
            l = 0, r = n - 1;
            while(l < r){
                //注意这里mid需要+1再除以2    加不加1完全取决于写的是l = mid，还是r = mid，和其他因素毫无关系。
                int mid = (l + r + 1) >> 1;
                if(a[mid] <= k) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", l);
        }
    }

    return 0;
}

浮点数
判断条件 r - l > 1e-8
输出double的六位小数 printf("%.6f\n", l);

#include <iostream>

using namespace std;

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

    double l = -100, r = 100;
    while(r - l > 1e-8){
        double mid = (l + r) / 2;
        if(mid * mid * mid >= n) r = mid;
        else l = mid;
    }

    printf("%.6f\n", l);

    return 0;
}

高精度加法

#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int> a, vector<int> b){
    vector<int> c;
    int n = a.size();
    int m = b.size();
    int i = 0, j = 0;
    int flag = 0;
    while(i < n && j < m){
        int tmp = a[i] + b[j] + flag;
        flag = 0;
        if(tmp >= 10){
            flag = 1;
            tmp -= 10;
        }
        c.push_back(tmp);
        i++;
        j++;
    }

    while(i < n){
        int tmp = a[i] + flag;
        flag = 0;
        if(tmp >= 10){
            flag = 1;
            tmp -= 10;
        }
        c.push_back(tmp);
        i++;
    }

    while(j < m){
        int tmp = b[j] + flag;
        flag = 0;
        if(tmp >= 10){
            flag = 1;
            tmp -= 10;
        }
        c.push_back(tmp);
        j++;
    }
    if(flag) c.push_back(flag);
    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--){
        printf("%d", C[i]);
    }
    //printf("\n");
    return 0;
}

简化一下模板

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(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

高精度减法

#include <iostream>
#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;
    int n = a.size();
    int m = b.size();
    int i = 0, j = 0;
    int flag = 0;
    while(i < n && j < m){
        int tmp = a[i] - b[j] + flag;
        flag = 0;
        if(tmp < 0){
            flag = -1;
            tmp += 10;
        }
        c.push_back(tmp);
        i++;
        j++;
    }

    while(i < n){
        int tmp = a[i] + flag;
        flag = 0;
        if(tmp < 0){
            flag = -1;
            tmp += 10;
        }
        c.push_back(tmp);
        i++;
    }

    //去掉多余的0，如12-12=00，12-11=01 
    while (c.size() > 1 && c.back() == 0) 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--){
        printf("%d", C[i]);
    }
    return 0;
}

因为a一定大于等于b，sub函数可以写的更简便一些。

vector<int> sub(vector<int> &a, vector<int> &b){
    vector<int> c;
    int flag = 0;
    for(int i = 0; i < a.size(); i++){
        int tmp = a[i] - flag;
        if(i < b.size()) tmp -= b[i];
        c.push_back((tmp + 10) % 10);
        if(tmp < 0) flag = 1;
        else flag = 0;
    }

    //去掉多余的0，如12-12=00，12-11=01 
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

高精度乘法

#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;
    cin >> a;
    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i--){
        A.push_back(a[i] - '0');
    }
    int b;
    cin >> b;

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

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

高精度除法

原本正常除法应该是从高位开始除，A[]应该从前往后存s比较好，但是一般高精度数的运算都是一起的，而加减乘都是从后往前存比较方便，所以这里A数组的处理不需要变，但是div函数的for循环要反过来处理。
最后得到的c也要反转一下才是之前的那种格式。

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

using namespace std;

vector<int> div(vector<int> &A, int b, int &r){
    vector<int> C;
    int t = 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() == 0) C.pop_back();
    return C;
}

int main(){
    string a;
    cin >> a;
    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i--){
        A.push_back(a[i] - '0');
    }
    int b;
    cin >> b;
    int r;
    vector<int> C = div(A, b, r);

    for(int i = C.size() - 1; i >= 0; i--){
        printf("%d", C[i]);
    }
    printf("\n%d\n", r);
    return 0;
}

前缀和

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int a[N], sum[N];

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++){
        sum[i] = sum[i-1] + a[i];
    }

    int l, r;
    for(int i = 0; i < m; i++){
        cin >> l >> r;
        printf("%d\n", sum[r] - sum[l - 1]);
    }
    return 0;
}

二维前缀和（子矩阵）

#include <iostream>

using namespace std;

const int N = 1010;

int a[N][N], s[N][N];

int main(){
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> 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];
        }
    }

    int x1, y1, x2, y2;
    for(int i = 0; i < q; i++){
        cin >> x1 >> y1 >> x2 >> y2;
        int res = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
        printf("%d\n", res);
    }
    return 0;
}

差分

#include <iostream>

using namespace std;

const int N = 100010;

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

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

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i] - a[i - 1];      //构建差分数组
    }

    int l, r, c;
    while(m--){
        cin >> l >> r >> c;
        b[l] += c;
        b[r + 1] -= c; 
    }

    for(int i = 1; i <= n; i++){
        a[i] = a[i - 1] + b[i];
        printf("%d ", a[i]);
    }
    return 0;
}

y总的模板
for (int i = 1; i <= n; i ) insert(i, i, a[i]);
对于这一行有些同学不理解，帮忙解释一下，其实是假定a数组最开始都是0，那么b数组初始时就是a数组的差分数组了，对于每一个a[i]，相当于插入了一个数，可以直接调用insert函数即可。
当然也可以从差分数组的定义出发，for(int i=1;i<=n;i) b[i]=a[i]-a[i-1]; 用这一行替换上一行，效果一样，只是上边的把a数组当成全为0，读入的a[i]再插入，这一个把读入后的当做a数组。

#include <iostream>

using namespace std;

const int N = 100010;
int n, m;
int a[N], 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 ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);
    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];
    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);
    return 0;
}

二维差分（差分矩阵）

#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[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c; 
}

int main(){
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            insert(i, j, i, j, a[i][j]);
        }
    }

    int x1, y1, x2, y2, c;
    while(q--){
        cin >> 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]);
            //这两种都可以 
            //a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
            //printf("%d ", a[i][j]);
        }
        printf("\n");
    }

    return 0;
}

双指针

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], s[N];

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

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

    return 0;
}

位运算

对于每个数字a，a&1得到了该数字的最后一位，之后将a右移一位，直到位0，就得到了1的个数
另外有一种lowbit方法 https://www.acwing.com/activity/content/code/content/40086/
解释 https://www.acwing.com/solution/content/2370/

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, x, k;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x;
        k = 0;
        while(x){
            k += x & 1;
            x = x >> 1;
        }
        cout << k << " ";
    }
    return 0;
}

离散化

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

using namespace std;

typedef pair<int, int> PII;
const int N = 300010; //开30万是因为add操作有10万次每次1个参数，query操作有10万次每次2个参数 

int n, m, x, c, l, r;
int a[N]; //离散化后的数组
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; //映射后的数组下标为1, 2, 3,...,n。 这样做是为了方便计算前缀和 
}

int main(){
    cin >> n >> m;
    while(n--){
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }

    while(m--){
        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());

    //将-10^9-10^9的alls映射到数组a 
    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), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    } 

    return 0;
}

区间合并

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

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

int n, l, r;
vector<PII> sets;

void merge(vector<PII> &sets){
    vector<PII> res;
    sort(sets.begin(), sets.end());
    int st = -2e9, ed = -2e9;
    for(auto item : sets){
        if(ed < item.first){
            if(st != -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}); //最后一个区间
    sets = res;
}

int main(){
    cin >> n;
    while(n--){
        cin >> l >> r;
        sets.push_back({l, r});
    }

    merge(sets);

    printf("%d\n", sets.size());

    return 0;
}