Meta Field
0%

算法模板

发表于 更新于 Valine：
本文字数： 6.4k 阅读时长 ≈ 6 分钟

ACWing

0x01 排序

快排模板

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
void quick_sort(int a[], int l, int r)
{
    if(l>=r) return ;
    int i = l-1, j = r+1, x = a[l+r >>1] ;
    while(i<j){
        do i++ ;while(a[i]<x) ;
        do j-- ;while(a[j]>x) ;
        if(i<j) swap(a[i],a[j]) ;
    }
    quick_sort(a,l,j),quick_sort(a,j+1,r);
}

快排题目785 （简单数组排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define MAX_SIZE 100002
using namespace std ;
int n ;
int a[MAX_SIZE];
void quick_sort(int a[],int l ,int r)
{
    if(l>=r) return ;
    int i = l-1, j = r+1 , x = a[l+r >>1] ;
    while(i<j){
        do i++ ;while(a[i]<x) ;
        do j-- ;while(a[j]>x) ;
        if(i<j) swap(a[i],a[j]) ;
    }
    quick_sort(a,l,j),quick_sort(a,j+1,r) ;
}

void print(int a[],int n){
    for(int i=1; i<=n;i++)
        cout<<a[i]<<" ";
}
int main(){
    cin >> n ;
    for(int i=1; i<=n; i++){
        cin >> a[i] ;
    }
    quick_sort(a,1,n) ;
    print(a,n);
    return 0 ;
}

归并模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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) {
        // 比较左右两部分的元素，将较小的放入临时数组tmp
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    }

    // 将剩余的左半部分的元素放入tmp
    while (i <= mid)
        tmp[k++] = q[i++];

    // 将剩余的右半部分的元素放入tmp
    while (j <= r)
        tmp[k++] = q[j++];

    // 将排序好的tmp数组复制回原数组q
    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];
}

归并习题 788逆序对数量

思想：分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
//先是都在mid左侧，然后是mid右侧，最后是mid两侧，加起来
using namespace std ;
typedef long long LL ;
const int MAX_SIZE = 100010 ;
int a[MAX_SIZE],tmp[MAX_SIZE];
LL merge_sort(int a[], int l, int r){
    if(l>=r) return 0;
    int mid = l+r >> 1 ;
    // 这里记得是LL
    LL res = merge_sort(a,l,mid) + merge_sort(a,mid+1,r) ;

    //归并过程
    int k=0, i=l, j = mid+1 ;
        
    while(i<=mid && j<=r){
        if(a[i]<=a[j]) tmp[k++] = a[i++] ;
        else{
            tmp[k++] = a[j++] ;
            res += mid-i+1 ;
        }
    }
    // 扫尾
    while(i<=mid) tmp[k++] = a[i++] ;
    while(j<=r) tmp[k++] = a[j++] ;
    // 物归原主
    for(int i=l, j=0; i<=r; i++,j++) a[i] = tmp[j] ;
    return res ;
}
int main()
{
    int n ;
    cin >> n ;
    for(int i=0; i<n; i++)
    {
        cin >> a[i] ;
    }
    cout<<merge_sort(a,0,n-1) ;
    return  0 ;
}

0x02 二分

整数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool check(int x){/*...*/} //检查x是否满足某种性质
//记忆
//男左女右，男是1，女是0
int SL(int l, int r)//结构LRL
{
    while(l<r)
    {
        int mid = l+r >> 1 ;
        if(check(mid)) r=mid ;
        else l = mid+1 ;
	}
    return l ;
}

int SR(int l, int r)//结构RLR
{
    while(l<r)
    {
        int mid = l+r+1 >> 1 ;
        if(check(mid)) l = mid ;
        else r = mid - 1 ;
	}
    return l ;
}

789数的范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
#define MAX_SIZE 100010
using namespace std ;
int a[MAX_SIZE] ;
int SL(int l, int r, int x){
    while(l<r){
        int mid = l+r >>1 ;
        if(a[mid]>=x) r=mid ;
        else l = mid+1 ;
    }
    return l ;
}

int SR(int l, int r, int x){
    while(l<r){
        int mid = l+r+1 >> 1;
        if(a[mid]<=x) l=mid ;
        else r = mid-1 ;
    }
    return r ;
}

int main(){
    int n, q ;
    cin >> n >> q ;
    for(int i=0; i<n; i++) cin>>a[i] ;
    for(int i=0; i<q; i++){
        int k ;
        cin >> k ;
        int l = SL(0,n-1,k) ;
        if(a[l]!=k) cout<<"-1 -1"<<endl ;
        else cout<<l<<" "<<SR(0,n-1,k)<<endl ;
    } 
    return 0 ;
}

浮点数二分

1
2
3
4
5
6
7
8
9
10
11
double S(double l, double r){
	const double eps = 1e-6 ;
	//具体看题目要求精度
	//保留4位=>1e-6,保留6位=>1e-8
	while(r-l>eps){
        double mid = (l+r)/2 ;
        if(check(mid)) r = mid ;
        else l = mid ;
    }
    return l ;
}

790开三次方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std ;

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

0x03 双指针

最普遍模板

1
2
3
4
for(i=0,j=0 ;i<=n; i++){
    while(j<i && check(i,j)) j++ ;
    /* ... */
}

思想核心：先想朴素的暴力算法，再将 简化为

799最长连续不重复子序列

最清晰题解链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<string.h>
#include<algorithm>
#define MAX_SIZE 100000
int a[MAX_SIZE] ;
int s[MAX_SIZE] ;
//s[]:动态统计每一个数字出现次数
using namespace std ;

int main(){
    int n ;
    int res = 0 ;
    cin >> n ;
    for(int i=0; i<n; i++) cin>>a[i] ;
    for(int i=0,j=0; i<n; i++){ //i表示终点,j表示起点
        s[a[i]]++ ;
        while(s[a[i]]>1){//有重复的数字后
            s[a[j]]-- ;//开始移动j
            j++ ;
        }
        res = max(res,i-j+1) ;
    }
    cout<<res<<endl ;
    return 0 ;
}

800 数组元素目标和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
const int N = 100010 ;
int a[N] ;
int b[N] ;
using namespace std ;

int main(){
    int n,m,x ;
    cin >> n >> m >> x ;
    for(int i=0; i<n; i++) cin >> a[i] ;
    for(int i=0; i<m; i++) cin >> b[i] ;
    for(int i=0,j=m-1; i<n; i++){//j从后往前查
        while(j>=0 && a[i]+b[j]>x){
            j--;
        }
        if(a[i]+b[j]==x){
            cout<<i<<" "<<j<<endl;
            break ;
        }
    }
    return 0 ;
}

2816判断子序列

子序列： 是 一个子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
const int N = 100010 ;
int a[N]; 
int b[N];
using namespace std ;

int main()
{
    int n, m ;
    cin >> n>> m ;
    for(int i=0; i<n; i++)cin>>a[i] ;
    for(int j=0; j<m; j++)cin>>b[j] ;
    int i=0 ;
    for(int j=0; j<m;j++){ //j指向b
        if(i<n && a[i]==b[j]) i++ ;
    }
    if(i==n) cout<<"Yes"<<endl ;
    else cout<<"No"<<endl ;
    return 0 ;
}

0x04 位运算

1
2
3
4
5
6
7
8
9
10
//求n的第k位数字
n>>k & 1
//返回n的最后一位1后所有位数(包含1)
// x & -x = x&(~x+1)
// eg: x=1010 lowbit(x) = 10 
// eg: x=101000 lowbit(x) = 1000 
int lowbit(int x)
{
	return x & -x ;
}

801 二进制中1的位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<string>
using namespace std ;
const int N = 100010 ;
int a[N] ;
int lowbit(int x){ // 核心
    return x& -x ;
}
int main(){
    int n ;
    cin>>n ;
    while(n--){
        int x ;
        cin>>x ;
        int res = 0 ;
        while(x)  x -= lowbit(x) , res++ ; // 每次减去x的最后一位1后面所有位（包含1）
        cout<<res<<" ";
    }
    return 0 ;
}

0x05 离散化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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, ...n
}

vector：单端数组，与普通数组区别在于 vector 可以动态拓展 ，其迭代器支持随机访问，常用的有 v.begin(), v.end()

v.begin()返回第一个元素的位置，v.end()返回

动态拓展：找更大的内存空间，将原有数据COPY到新空间并释放原空间。

image-20240213221243575

1
2
3
4
vector<T> v ;				//采用模板实现类实现，默认构造函数
vector(v.begin(),v.end());	  //将v[begin,end)区间中的元素拷贝给本身
vector(n,elem);				//构造函数将n个elem拷贝给本身
vector(const vector &vec);	  //拷贝构造函数
-------------本文结束感谢您的阅读-------------
请作者喝一杯蜜雪冰城吧！