基础算法模板

290次阅读
没有评论

共计 3306 个字符,预计需要花费 9 分钟才能阅读完成。

内容目录

排序

  • 快速排序
  • 归并排序

快速排序

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

归并排序

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]) temp[k++] = q[i++];
        else temp[k++] = q[j++];

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

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

二分

  • 整数二分
  • 浮点数二分

整数二分

bool check(int x) {
    // 检查x是否满足某种性质
}

// 区间[l,r]被划分成[1,mid]和[mid+1,r]时使用
int bsearch_1(int l,int r){
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid; // check判断mid是否满足某一性质
        else l = mid + 1;
    }
    return l;
}

// 区间[l,r]被划分成[l,mid-1]和[mid,r]时使用
int bsearch_2(int l,int r){
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分

bool check(double x){
    // 检查x是否满足某种性质
}

double bsearch_3(double l,double r){
    // eps表示精度,取决于题目的要求
    const double eps = 1e-8;
    while(r - l > eps){
        double mid = (l + r) /2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度运算

  • 高精度加法
  • 高精度减法
  • 高精度乘法
  • 高精度除法

高精度加法

vector<int> add(vector<int>& A,vector<int>& B){
    int t = 0;
    vector<int> C;
    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;
}

高精度减法

vector<int> sub(vector<int> &A,vector<int> &B){
    int t = 0;
    vector<int> C;
    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;

}

高精度乘法

// A * b : A是大数,b是小数
vector<int> mul(vector<int> &A,int b){
    int t = 0;
    vector<int> C;
    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;
}

高精度除法

// A / b : A是大数,b是小数,C为商,r为余数
vector<int> div(vector<int> &A, int b, int &r){
    r = 0;
    vector<int> C;
    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;
}

前缀和

  • 一维前缀和
  • 二维前缀和

一维前缀和

// 求数组a中[l,r]区间的元素和
// 为方便处理,下标从1开始进行处理
s[i] = a[1] + a[2] + ... + a[i]
a[l] + ... + a[r] = s[r] - s[l-1]

二维前缀和

// 给定二维数组a[i][j],求以(x1,y1)为左上角,(x2,y2)为右下角的子矩阵和
// 下标从1开始处理
s[i][j] = 坐标(i,j)的左上部分的所有元素和

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

以(x1,y1)为左上角,(x2,y2)为右下角的子矩阵和

s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

差分

  • 一维差分
  • 二维差分

一维差分

// 给[l,r]区间的所有数都加上c
b[l] += c;
b[r+1] -= c;

二维差分

// 给左上角(x1,y1),右下角为(x2,y2)的子矩阵都加上c
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;

双指针

for(int i = 0, j = 0; i < n; i++){
    while( j <= i && check(i,j) ) j++;
    /*
    * 对于题目的具体逻辑处理
    */
}
常见问题分类:
    (1) 对于一个序列,用两个指针维护一段区间
    (2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

位运算

x的二进制第k位

// 1. 将二进制数x右移k位:res = x >> k
// 2. 将结果对1进行取与运算: res = res & 1
// 合起来:
res = x >> k & 1;

lowbit(x) 运算

// lowbit(x):返回x的最后一位1及其之后的数据
// x = 42(十进制) = 101010(二进制)
// lowbit(x) = 10(二进制) = 2(十进制)
res = x & -x;

可以使用$lowbit(x)$运算求$x$二进制表示中有几个1:

// ans: x的二进制表示中1的个数
int ans = 0;
while(x){
    x -= lowbit(x);
    ans++;
}

离散化


// 将alls数组中的元素映射到[1 , ... , alls.size()]

// 去重
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());

// return: x的映射后的值
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;
}

区间合并

void merge(vector<PII> &segs){
    vector<PII> res;
    // 依据左端点进行排序
    sort(segs.begin(),segs.end());
    // 起始区间为负无穷
    int st = -2e9, ed = -2e9;

    for(auto seg: segs){
        if(seg.first > ed){
            if(st != -2e9){
                res.push_back({st,ed});
            }
            st = seg.first;
            ed = seg.second;
        }else{
            ed = max(ed,seg.second);
        }
    }
    if(st != -2e9){
        res.push_back({st,ed});
    }
    segs = res;
}
正文完
 
PG Thinker
版权声明:本站原创文章,由 PG Thinker 2023-09-15发表,共计3306字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
热评文章