常用算法总结

1mb=1024kb

1kb=1024b

1b=8bits

大题两模拟，bfs，数论，dp，二分，贪心，并查集

1.由数据范围反推算法复杂度以及算法内容

image-20220405182811869

2^20=1000000

2^15=32768

2^16=65536

2^63=10^18

数据范围

image-20220405153243398

long long内的最大阶乘20 ! 20!20!
int内的最大阶乘12 ! 12!12!

数论基础

1.欧几里得算法

求两个正整数的最大公约数和最小公倍数 时间复杂度 O(logn)

1
2
3
4
5
6
7
8
9
//最大公约数
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
//最小公倍数
int lcm(int a,int b){
	return a*b/gcd(a,b);
}

演示代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstdio>
using namespace std;

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

int lcm(int a,int b){
	return a*b/gcd(a,b);
} 
int main()
{
	int a,b;
	cin>>a>>b;
	cout<<gcd(a,b)<<" ";
	cout<<lcm(a,b);
	return 0;
}

2. 扩展欧几里得算法

裴蜀定理
扩展欧几里德算法是用来在已知a , b 求解一组x , y 使它们满足贝祖（裴蜀）等式： a x + b y = gcd ⁡ ( a , b )

1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

输入a b输出满足裴蜀等式的x y

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
#include <iostream>
#include <algorithm>

using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
//    int n;
//    scanf("%d", &n);
//
//    while (n -- )
//    {
        int a, b;
        scanf("%d%d", &a, &b);
        int x, y;
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
//    }

    return 0;
}

3. 线性筛素数

可以在 O(n) 的时间复杂度内求出 1∼n之间的所有质数。

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
/*
线性筛素数
求1到n中所有质数，以及每个数的最小值因子 
时间复杂度o(n) 
筛掉的一定是合数，一定用其最小质因子筛的 
*/
#include<iostream>
using namespace std;
const int N=1000010 ; 
int primes[N], cnt;//存所有质数 
bool st[N];//当前数有没有被筛过 

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )//从小到大枚举所有质数 
        {
            st[primes[j] * i] = true;//primes[j]一定小于等于i的j因子 
            if (i % primes[j] == 0) break;//
        }
    }
}

 
int main()
{
	int n;
	cin>>n;
	get_primes(n); //求1到n的所有质数和质数个数 
		for(int i=0;i<cnt;i++){ 
			printf("%d\n",primes[i]);
		}
		cout<<"个数："<<cnt;//cnt为从1到n有多少个质数 
		return 0;
}

4 算数基本定理

image-20220405164918295

5 杨辉三角

image-20220405165336304

image-20220405165357663

6 约数个数和约数之和

image-20220405184125413

P是质数

举例：

image-20220405184558501

输入n输出n的约数的个数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
using namespace std;
int dividedCount(int x) {
    int ans = 1;
    for (int i = 2; i <= x / i; ++i) {
        if (x % i == 0) {
            int s = 0;
            while (x % i == 0) x /= i, ++s;
            ans *= (s + 1);
        }
    }
    if (x > 1) ans *= 2;
    return ans;
}
int main()
{
	int n;
	cin>>n;
	cout<<dividedCount(n);
}

输入n求n的约数的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
using LL = long long;
const int MOD = 1e9 + 7;
int dividedSum(int x) {
    LL ans = 1;
    for (int i = 2; i <= x / i; ++i) {
        LL t = 1;
        while (x % i == 0) x /= i, t = (t * i + 1) % MOD;
        ans = ans * t % MOD;
    }
    if (x > 1) ans = ans * (x + 1) % MOD;
    return ans;
}

int main()
{
	int n;
	cin>>n;
	cout<<dividedSum(n);
	return 0;
}

7 前缀和

一维数组

前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化

image-20220405201419796

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//求n个数的数列中从第l个数到第r个数的值
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
int main()
{
	int n,l,r;
	cin>>n; 
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	
	for(int i=1;i<=n;i++)
	{ 
    sum[i]=sum[i-1]+a[i];   
	}
	scanf("%d%d",&l,&r);

 printf("%d\n", sum[r]-sum[l-1]);

}

二维前缀和

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

同一维前缀和一样，我们先来定义一个二维数组s[] [], s[i] [j]表示二维数组中，左上角(1,1)到右下角( i,j )所包围的矩阵元素的和。接下来推导二维前缀和的公式。

8 差分

一维差分

类似于数学中的求导和积分，差分可以看成前缀和的逆运算

首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];

然后我们构造一个数组b ： b[1] ,b[2] , b[3],,,,,, b[i];

a[1]=b[1]

a[2]=b[1]+b[2];

a[3]=b[1]+b[2]+b[3]

使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]

也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。

1
a[0 ]= 0;

b[1] = a[1] - a[0];

b[2] = a[2] - a[1];

b[3] =a [3] - a[2];

1
........

b[n] = a[n] - a[n-1];

数位处理

判断日期的合法性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check_valid(int year, int month, int day)
{
    if (month == 0 || month > 12) return false;
    if (day == 0) return false;
    if (month != 2)
    {
        if (day > days[month]) return false;
    }
    else
    {
        int leap = year % 100 && year % 4 == 0 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }

    return true;
}

逆序数：

image-20220406203220677

第十二届蓝桥杯-直线

image-20220407203813312

y=kx+b

枚举不同的截距和斜率

对于垂直的直线斜率不存在

image-20220407204331015

image-20220407204550081

货物摆放

小蓝有一个超大的仓库，可以摆放很多货物。

现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝

规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、

宽、高。

小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上

分别堆 L、W、H 的货物，满足 n = L × W × H。

给定 n，请问有多少种堆放货物的方案满足要求。

例如，当 n = 4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、

2 × 2 × 1、4 × 1 × 1。

请问，当 n = 2021041820210418 （注意有 16 位数字）时，总共有多少种

方案？

image-20220407205824847

把 1∼n 这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入样例：

1
3

输出样例：

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include<algorithm>
using namespace std;
const int N=10;
int a[N];
int main() {
    int n;
    cin>>n;
	for(int i=0;i<n;i++){
	    a[i]=i+1;
	}
	sort(a,a+n);
	do{
		for(int i=0;i<n;i++)
		    cout<<a[i]<<" ";
		cout<<endl;
	}while(next_permutation(a,a+n));
	return 0;
}

二分法

数的范围

给定一个按照升序排列的长度为 n 的整数数组，以及 q个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1

输入格式

第一行包含整数 n和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式

共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1

数据范围

1≤n≤100000
1≤q≤10000
1≤k≤10000

输入样例：

1
2
3
4
5
6 3
1 2 2 3 3 4
3
4
5

输出样例：

1
2
3
3 4
5 5
-1 -1
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
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

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

    for (int i = 0; i < m; i ++ )
    {
        int x;
        scanf("%d", &x);
        // 二分x的左端点
        int l = 0, r = n - 1;   // 确定区间范围
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if (q[r] == x)
        {
            cout << r << ' ';

            // 二分x的右端点
            r = n - 1;  // 右端点一定在[左端点, n - 1] 之间
            while (l < r)
            {
                int mid = l + r + 1 >> 1;   // 因为写的是l = mid，所以需要补上1
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << r << endl;
        }
        else cout << "-1 -1" << endl;
    }

    return 0;
}

二分法第一步确定区间范围:

1
2
int l=0;
int r=n-l;

2:当r>l的时候，取r 和 l 的中心点mid

1
2
3
4
5
while(r>l)
{
int mid=r+l>>1;右移一位相当于除以2

}

3 判断某个数在断点的右区间还是左区间

1
2
3
4
if(p[mid]<=x){//x在区间的右端点
l=mid;
    
}
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
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

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

    for (int i = 0; i < m; i ++ )
    {
        int x;
        scanf("%d", &x);
        // 二分x的左端点
        int l = 0, r = n - 1;   // 确定区间范围
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if (q[r] == x)
        {
            cout << r << ' ';

            // 二分x的右端点
            r = n - 1;  // 右端点一定在[左端点, n - 1] 之间
            while (l < r)
            {
                int mid = l + r + 1 >> 1;   // 因为写的是l = mid，所以需要补上1
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << r << endl;
        }
        else cout << "-1 -1" << endl;
    }

    return 0;
}

最大取到的数

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

1
m和n最大不能组成的数字=(m-1)*(n-1)-1