Template

AcWing
Start: 2024.10.24
End: Doing
Plan: Variable Time
Check:

章节：课节	1	2	3	4	5	6
一、基础算法	10.24		习一		\	\
二、数据结构		习二		习三		\
三、搜索与图论		习四				\
四、数学知识			习六			习七
五、动态规划			习八		\	\
六、贪心			\	\	\	\
七、时空复杂度分析		\	\	\	\	\

注：习 X 指第 X 周的习题课。

一、基础算法

1. 快速排序

#include <iostream>
using namespace std;
const int N = 100010;
int 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);	// 最终两边都可以有 x，因此快速排序是不稳定的（要稳定，只需要使得唯一,改成 pair）
        if(i<j) swap(q[i], q[j]);
    }
    
    quick_sort(q, l, j);
    quick_sort(q, j+1, r);
}

int main(){
    int n;
    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]);
    return 0;
}

注意：

不能随意搭配，只有下面两种：

int x = q[l+r>>1];
quick_sort(q, l, j);
quick_sort(q, j+1, r);

int x = q[l+r+1>>1];
quick_sort(q, l, i-1);
quick_sort(q, i, r);

2. 归并排序

#include <iostream>
using namespace std;
const int N = 100010;
int a[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(i=l, k=0; i<=r; i++, k++) q[i] = tmp[k];
}

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

拓展：本模版，可以用来计算所有的逆序对数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], tmp[N];
unsigned long ans = 0;	// 用 ul

// 利用归并排序
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++], ans += mid-i+1; // 只添加了一句
 }
 while(i <= mid) tmp[k++] = q[i++];
 while(j <= r) tmp[k++] = q[j++];

 for(i=l, k=0; i<=r; i++,k++) q[i] = tmp[k];
}


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

 merge_sort(a, 0, n-1);

 cout << ans;    // 输出ul 用cout
 return 0;
}

3. 二分

查找有序序列中的某数的范围下标。

#include <iostream>
using namespace std;

const int N = 100010;
int a[N];

// 二分查找（避免 mid+1）在长度为 n 的数组 q 中查找数字 m 的下标范围
void query(int q[], int n, int m){
    // 先找第一个出现的 m
    int l = -1, r = n;  // 注意
    while(l+1 != n){
        int mid = l+r>>1;
        if(q[mid] >= m) r = mid;	// 把所求的 m 包在答案范围里，不断去逼近
        else l = mid;
    }
    // 若找到，则 r 就是第一个 m
    if(q[r] != m){
        printf("-1 -1\n");
        return;
    }
    printf("%d", r);
    // 下面找最后一个出现的 m
    l = -1, r = n;
    while(l+1 != r){
        int mid = l+r>>1;
        if(q[mid] <= m) l = mid;
        else r = mid;
    }
    // 则 l 就是最后一个 m
    printf("%d\n", l);
}

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

对于浮点数，反而更简单了，根本不存在mid+1的困扰（虽然上述也解决了这个问题）

下面是求浮点数的三次方。（数字范围在 -10000到10000之间）

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

double aaa(int a) {return a*a*a; }

int main(){
    double n;
    cin >> n;
    
    double l = -10000, r = 10000;
    while(r-l > 1e-8){
        double mid = (l+r)/2;
        if(aaa(mid) >= n) r = mid;	// 向 n 逼近
        else l = mid;
    }
    cout << fixed << setprecision(6) << r;	// l 或 r 均可
    
    return 0;
}

模版：

int L=-1, R=n;
while(L+1 != R){
    int mid = L+R>>1;
    if(check()) R = mid;
    else L = mid;
}
// 使用 L/R 处理....

参考：https://blog.csdn.net/WJPnb1/article/details/126360962

4. 高精度

二、数据结构

三、搜索与图论

四、数学知识

五、其他