一些蒟蒻的模板

WBCMZ / 2023-08-16 / 原文

快速排序

平时写题用sort就行了，但是如果要求排序就中间结果诸类的题，还是有点用！

听说long long ago，高中组的比赛只要会打sort代码就能得分（当时不允许用STL）

我也想比赛考这样的题……

快排主要还是边界问题

为了防止快排退化为冒泡，可以采用随机数（不过平时我还是习惯取中间值……）

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,q[N];
void quick_sort(int q[],int l,int r){
    if(l>=r) return;
    int x=q[l+r>>1];
    int 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(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    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;
}

归并排序

同上，也可以用STL提供的merge

但是这个相对还是用处多一点的

且归并排序的重点不在于边界

合并的过程很重要（要开辅助空间）

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
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(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    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

当我们将区间 [l,r] 划分成 [l,mid] 和 [mid+1,r] 时，其更新操作是 r=mid 或者 l=mid+1

计算 mid 时不需要加1！！！

int bsearch_1(int l,int r){
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    return l;
}

模板 2

当我们将区间 [l,r] 划分成 [l，mid-1] 和 [mid,r]时，其更新操作是 r=mid-1 或者 l=mid

此时为了防止死循环，计算mid时需要加1！！！

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

二分小结

模板1就是在满足chek()的区间内找到左边界

模板2在满足check()的区间内找到右边界

然后无论是左边界还是右边界，都应该是整个区间中某一段满足某性质（如单调不降）与另一段不满足该性质的分界点

假设有一个总区间，经由我们的 check 函数判断后，可分成两部分，

这边以o作 true，.....作 false 示意较好识别

如果我们的目标是下面这个v，就必须使用模板 1

................vooooooooo

假设经由 check 划分后，整个区间的属性与目标v如下，则我们必须使用模板 2

oooooooov...................

所以下次可以观察 check 属性再与模板1 or 2 互相搭配就不会写错啦

快速幂