该文章长期更新

1. STL

1. vector（万能动态数组）

1
2
3
4
5
6
7
vector<int> v;          // 声明
v.push_back(3);         // 尾部插入
v.pop_back();           // 尾部删除
v.size();               // 元素个数
v[0] = 5;               // 随机访问（不检查越界）
sort(v.begin(), v.end());// 排序
range::sort(v);          // 排序 C++20新特性

2. string（字符串处理）

1
2
3
4
5
6
string s = "abc";
s += "def";             // 拼接
s.substr(1, 2);         // 取子串（位置,长度）
s.find("cd");           // 查找（返回位置）
stoi(s);                // 字符串转数字
s = to_string(123);     // 数字转字符串

3. priority_queue（优先队列/堆–最小堆）

1
2
3
4
5
6
7
priority_queue<int> pq;  // 默认大根堆
pq.push(3);             // 插入
pq.top();               // 取堆顶
pq.pop();               // 弹出堆顶
// 小根堆定义
priority_queue<int, vector<int>, greater<int>> min_pq;

4.(1). map（红黑树–平衡二叉搜索树）

1
2
3
map<string, int> mp;
mp["apple"] = 5;        // 插入/修改
auto it = mp.find("apple");  // 查找（返回迭代器）

4.(2). unordered_map（哈希表–数组 + 链表/红黑树桶）

1
2
3
4
5
6
unordered_map<string, int> mp;
mp["apple"] = 5;        // 插入/修改
mp.count("apple");      // 判断是否存在
mp.erase("apple");      // 删除
for(auto &[k,v] : mp)   // 遍历（C++17）
    cout << k << " " << v;

5. set（自动排序集合）

1
2
3
4
5
set<int> s;
s.insert(3);            // 插入
s.count(3);             // 是否存在
s.erase(3);             // 删除
// 自动排序，可直接用*s.begin()取最小值

2. 排序

最简模板

  1. 二分查找
1
2
3
sort(v.begin(), v.end());
auto it = lower_bound(v.begin(), v.end(), x);
if(it != v.end() && *it == x) // 找到x
  1. 自定义排序（贪心常用）
1
2
bool cmp(int a, int b) { return a > b; }
sort(v.begin(), v.end(), cmp);
  1. 结构体排序
1
2
3
4
5
struct Node { int x, y; };
vector<Node> v;
sort(v.begin(), v.end(), [](Node a, Node b){
    return a.x == b.x ? a.y < b.y : a.x > b.x;
});

💡 优先掌握 vector + sort + priority_queue，其他遇到现查即可！

在快速的时间下，三种重要的排序，计数排序，快速排序，自定义排序

计数排序

计数排序是一种特殊的桶排序。
计数排序的工作原理是使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数，然后根据数组 C 来将 A 中的元素排到正确的位置。
它的工作过程分为三个步骤：

  1. 计算每个数出现了几次；
  2. 求出每个数出现次数的前缀和；
  3. 利用出现次数的前缀和，从右至左计算每个数的排名。
    这样时间复杂度是 $O(max(n,w))$，w 表示排序中最大的那个数。
    计数排序的时间复杂度小，但空间复杂度极大，当 w 是大于 $10^7$ 时就不建议使用计数排序，会导致空间溢出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int a[N];
int C[N];//此时的N要保证比a数组中的任何一个数都要大。
for(int i=1;i<=n;i++)c[a[i]]++;
int t=0;
for(int i=0;i<=w;i++)
{
	if(c[i]>0)
	{
	while(c[i]>0){
		a[++t]=i;
		c[i]--;
	}
	}
}

时间复杂度 $O(max(n,w))$。

快速排序

定义：

快速排序（英语：Quicksort），又称分区交换排序（英语：partition-exchange sort），简称「快排」，是一种被广泛运用的排序算法。

过程：

快速排序的工作原理是通过分治的方式来将一个数组排序。
对于一个数列，我们找到一个中间位置的值 $x$ ，通过划分区间，比 $x$ 小的放在左边，比 $x$ 大的放在右边。然后在分别递归这两个区间，按照上述做法，直到递归到区间只有 $1$ 个数时，终止递归，再由开始分出来的区间，依次合并，构成的序列就是一个完美的拍好序的数列，完结撒花。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void k_sort(int x, int y)
{
    int mid = a[(x + y) >> 1];
    int i = x, j = y;
    while (i <= j)
    {
        while (a[i] < mid)
            i++;
        while (a[j] > mid)
            j--;
        if (i <= j)
        {
            q = a[i], a[i] = a[j], a[j] = q, i++, j--;
        }
    }
    if (x < j)
        k_sort(x, j);
    if (i < y)
        k_sort(i, y);
    return;
}

时间复杂度分析：
在平均情况下，快速排序的时间复杂度是 $O(n \log n)$ 。这是因为每次划分都将数组分成两个大致相等的部分，递归的深度是 $log\ n$（其中 $n$ 是数组的长度），而每一层的划分操作需要 $O(n)$ 的时间。

快排在极端最坏情况下会退化成 $n^2$，当然这种情况很少，如果用到快排做题最好直接使用 sort 函数。

这边建议如果快排不太懂可以直接使用 sort 函数，很好用，后面的自定义排序也是基于这个函数当然比赛你也可以手搓快排。

自定义排序

自定义排序是排序中最重要的一部分

自定义排序主要是基于 sort 函数。

sort函数

在 sort 函数里不加别的参数时，默认是按权值从小到大排。

1
2
sort(a+1,a+n+1);//表示把数组 a 从 1-n 按从小到大排好序
//两参数：[数组名+初始位置下标,数组名+元素个数+初始位置下标]

sort 里面可以加一个函数名用来实习自定义排序

1
2
3
4
5
6
7
bool cmp(int x,int y)
{
	return x>y;//实现从大到小排序

	//return abs(x-1000)>abs(y-1000);实现f(x) = |x-100| 的排序
}
sort(a+1,a+n+1,cmp);

同样自定义函数可以是调用一个结构体函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 123456;
struct student {
int score;
int math,chinese,english;
};
student a[N];
bool cmp(student x,student y)
{
	if(x.score==y.score)
	{
		if(x.math==y.math)return x.chinese>y.chinese;
		return x.math>y.math;
	}
	return x.score>y.score;
}
sort(a+1,a+n+1,cmp);

自定义排序可以很复杂，配合上结构体可以完成很多的操作，很重要。

3. 二分

定义

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

过程

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

示例概念

二分是什么概念呢，举个例子，比如你在心里想一个 $1000$ 以内的正整数，让我猜，我每次猜一个数，你需要回答大了还是小了，这样，我可以做到最多 $10$ 次我就可以猜到这个数字是多少。
它的猜数路线是这样的，比如你猜的一个数是 $147$ ，我第一次猜 $500$ ，发现是大了，那么下次我猜的范围就是 $1-499$ ，我再猜 $250$ ，那么下次范围就是 $1-249$ ，再猜 $125$ ，下次范围是 $126-149$ ，再猜 $138$ ，下次范围 $139-149$ ，再猜 $144$ ，下次范围就是 $145-149$ ，再猜 $147$ ，这样就猜中了，只用了 $6$ 次就出结果了。换成 $1000$ 以内的任何数都是这样，都可以保证在 $10$ 次以内猜中。倘若一个个的试探的话，最坏可能会 $1000$ 次才能猜出来结果。这样对比二分的效率就来了，对应到代码上：

非二分

1
2
3
4
5
6
7
8
9
10
int x;
cin>>x;//要猜的数

for(int i=1;i<=1000;i++)
	if(i==x)
	{
		cout<<"猜对了";
		break;
	}

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int x;
cin>>x;//要猜的数

int l=1,r=1000;//猜数的左右边界

while(l<=r)
{
	int mid = (l+r)/2;//每次猜的数是中间值，依次可以对半划分范围
	if (mid==x){
	cout<<"猜对了";
	break;
	}
	if (mid>x) r=mid-1;//mid比x大，说明下次猜数要从 [l,mid-1]中选择
	else l=mid+1; //mid比x小，说明下次猜数要从 [mid+1,r]中选择
}

那么假设我们猜的数范围是 $[1,n]$ ，那么非二分的做法时间复杂度就是 $O(n)$ ，而对于二分做法，每次猜都会缩减一半的范围，一直缩到范围为这个数本身，那么设时间为 $t$ ，那么 ， $2^t=n,t=\log_2(n)$，即时间复杂度为 $O(log(n))$ 。

如何观察到需要用二分

观察上个例子，为什么二分可以比一个个查询的速度快，其实就是它舍弃了一些不用查的数据，而且可以保证这部分数据绝对不会在答案中，而如何可以保证我们舍弃的数据绝对不会被查到，所以需要满足单调性，对于这个猜数问题它满足的是数据的单调性，还有一种单调性是状态决策的单调性（即答案的单调性），例题：P0003 拍照分组。

当一个状态的决策过程或者序列满足单调性它往往可以考虑使用二分来解决。

STL 形式：

  • lower_bound(a,a+n,x)-a; 表示在 $a$ 数组中找到第一个大于等于 $x$ 数的位置。
  • upper_bound(a,a+n,x)-a; 表示在 $a$ 数组中找到第一个大于 $x$ 数的位置。

参考模版

1
2
3
4
5
6
7
8
9
int l=1;r=n;
int ans;//个人习惯，ans表示当前答案满足时的最优解
while(l<=r)
{
   int mid=(l+r)>>1;
   if(check(mid))
    l=mid+1,ans=mid;
    else r=mid-1;
}

4.1 前缀和

定义：前缀和数组 s[i] 表示从数组开始到第 i 个元素的累加和。

使用场景：

  • 快速计算区间和。

示例问题：区间和查询

问题描述：给定一个数组和若干查询，每次查询给出区间 [l, r]，求该区间的和。

实现步骤：

  • 预处理前缀和数组。
  • 对于每次查询，利用公式 sum[l, r] = s[r] - s[l-1] 计算区间和。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int N = 10000001;
int a[N];
int s[N];
int n, m, ans;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i], s[i] = s[i - 1]+a[i];
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        cout << s[y] - s[x - 1] << "\n";
    }
    return 0;
}

4.2 差分

定义：差分数组 d[i] 表示原数组相邻两项的差值。

使用场景：

  • 修改区间值时避免暴力遍历。

示例问题：区间加法

问题描述：给定一个数组和若干操作，每次操作对区间 [l, r] 的每个元素加上一个值 k。

实现步骤：

  • 初始化差分数组。
  • 对每次操作，在差分数组中修改对应位置。
  • 根据差分数组还原原数组。

示例代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N = 101001;

int n, m, ans;
int a[N], d[N],q[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        d[i] = a[i] - a[i - 1];
    while (m--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        d[l] += c;     // 给l端点的差分值+c
        d[r + 1] -= c; // 给r+1端点的差分值-c
    }
    for (int i = 1; i <= n; i++)
        q[i] = q[i - 1] + d[i];
    for (int i = 1; i <= n; i++)
    {
        cout << q[i] << " ";
    }
    return 0;
}

前缀和和差分主要用于思想优化和一些别的算法结合到一起。

5.数学

筛质数

埃氏筛素数

1
2
3
4
5
6
7
8
vector<int>p;
    for (int i = 2; i <= N; i++)
        if (!a[i])
        {
        p.push_back(i);
        for (int j = i+i; j <= N; j += i)
                a[j] = 1;
        }

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
void get_primes()
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])primes[++cnt]=i;
        for(int j=1;primes[j]<=n/i;j++)//保证每个数只会被最小质因子筛掉
        {
            st[primes[j]*i]=1;
            if(i%primes[j]==0)break;
        }
    }
    return ;
}

而为什么线性筛的复杂度是O(n)，埃氏筛是O(nloglogn)，是因为线性筛中每个数只可能被筛掉一次。
因为一个数是被其最小质因子筛掉，那么就算一个数存在两个及以上的质因子，只要最小的把这个数筛过，那么就不会用其他的质因子筛掉这个数。
如 ：21
埃氏筛会被3和7分别筛掉，想当于21被筛了两次
而线性筛只会被筛掉一次，因为质数是从小到大开始枚举，一旦出现i%primes[j]就会退出循环，根本枚举不到更大的质因子。

分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void divide(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            int s=0;
            while(x%i==0)
            {
                x/=i;
                s++;
            }
            cout<<i<<" "<<s<<"\n";
        }
    }
    if(x>1) cout<<x<<" "<<1<<"\n";
    cout<<"\n";
    return ;
}

快速幂

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1001;
int a, b, p;
int n, m, ans;
int t;
void qmi()
{
    int res = 1 % p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b /= 2;
    }
    cout << res << "\n";
}
signed main()
{
    cin >> t;
    while (t--)
    {
        cin >> a >> b >> p;
        qmi();
    }
    return 0;
}

为什么需要用到逆元？

{
因为要求$(a/b)\quad mod\quad p$ ，由于涉及到了除法，就需要把除法转化为乘法，那么$a \times b^{-1} \quad mod \quad p$ ，但是这里的$b^{-1}$ 并不是指倒数，只要满足 $b \times x \equiv 1 (mod\quad p)$ 即可，那么 $x$ 就是 $b$ 的逆元即 $x\equiv b^{-1}(mod \quad p)$ ，有费马小定理可得，$b$ 的逆元为 $b^{p-2}$ 。
}
求逆元：$x=m/gcd(m,b)$
费马定理：$b^{p-1}=1(mod\quad p)$

组合数学

朴素法求组合数：$O(n^2)$

适用范围：
1 \leq n \leq 10000 ,
1 \leq a,b \leq 20000

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

using namespace std;

const int N=2010,mod=1e9+7;

int c[N][N];//将所有的组合方式都预处理出来

void init()
{
    for(int i=0;i<=2000;i++)
     for(int j=0;j<=i;j++)
      if(!j) c[i][j]=1;
      else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}

int main()
{
    int n;
    scanf("%d",&n);

    init();

    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",c[a][b]);
    }

    return 0;
}

快速幂求组合数: $O(nlogn)$

适用范围：
$$
1 \leq n \leq 10000 ,
1 \leq a,b \leq 10^5
$$

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
#include <bits/stdc++.h>
using namespace std;
const int N = 101001;
typedef long long LL;
int n, m, ans;
int fact[N], infact[N];
const int mod = 1e9 + 7;
int qmi(int a, int b)
{
    int res = 1 % mod;
    while (b)
    {
        if (b & 1)
            res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b /= 2;
    }
    return res;
}
int main()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;//分子的阶乘
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2) % mod;//逆元的阶乘
    }
    /*求逆元优化成线性
    infact[N - 1] = qmi(fact[N - 1], mod - 2);
    for (int i = N - 2; i >= 1; i--)
    {
        infact[i] = (LL)infact[i + 1] * (i + 1) % mod; // 分母的阶乘
    }*/
    cin >> n;
    while (n--)
    {
        int a, b;
        cin >> a >> b;
        cout << (LL)fact[a] * infact[b] % mod * infact[a - b] % mod << "\n";
    }
    return 0;
}

6.1 并查集

1. 概述

并查集（Union-Find），也称为不相交集（Disjoint Set Union，DSU），是一种数据结构，主要用于处理集合的合并（union）与查询（find）操作。它支持高效地处理某些动态连通性问题，例如判断两个元素是否在同一集合中，或者将两个元素合并到一个集合中。

并查集常用于处理图论中的连通性问题、网络中元素的关系查询等问题。它通常用于图的最小生成树（MST）算法（如 Kruskal 算法），网络连接问题等。

2. 基本操作

并查集支持以下基本操作：

  • Find：查找某个元素所在的集合。通常通过查找元素的“父节点”来实现。
  • Union：将两个元素所在的集合合并为一个集合。

这些操作通常都要求在尽可能短的时间内完成。

3. 数据结构

并查集的核心思想是每个元素在集合中都有一个父节点。最初每个元素自成一个集合，父节点指向自己（即每个集合的代表元素是自己）。合并集合时，会将其中一个集合的根节点指向另一个集合的根节点。

为了提高效率，通常使用两个技术来优化并查集的操作：

  1. 路径压缩（Path Compression）：在查找操作时，使得路径上的每个节点都直接指向根节点，从而加快后续查找的速度。
  2. 统计联通块数量：在合并操作时，将不同的两个集合合并到一起，并统计这个集合有多少数目

4. 并查集的实现

以下是并查集的常见实现：
c++

1
2
3
4
5
6
int find(int x)//
{
	if (f[x] == x)
		return x;
	return f[x] = find(f[x]); // 找祖宗的祖宗，递归到最深层返回
}

模版

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
#include <bits/stdc++.h>
using namespace std;
const int N = 101001;
int f[N];
int n, m, ans;
int find(int x)
{
	if (f[x] == x)
		return x;
	return f[x] = find(f[x]); // 找祖宗的祖宗，递归到最深层返回
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		f[i] = i;
	while (m--)
	{
		int x, y;
		char op;
		cin >> op >> x >> y;
		if (op == 'Q')
		{
			int a = find(x), b = find(y);
			if (a == b)
				cout << "Yes\n";
			else
				cout << "No\n";
		}
		else
		{
		int a = find(x), b = find(y);
			f[a]=b;
		}
	}
	return 0;
}

6.2 贪心引入

贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

解释

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

证明

贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。

  1. 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
  2. 归纳法：先算得出边界情况（例如 n==1）的最优解，然后再证明：对于每个 n ,$f_{n+1}$ 都可以由 $f_{n}$ 推导出结果。

要点

在算法竞赛中，最常见的贪心有两种。

  • 我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。
  • 我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）

二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。

排序解法

用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。

后悔解法

思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

与动态规划区别

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

例题

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

P1080 [NOIP 2012 提高组] 国王游戏 - 洛谷

看到任意排列想到邻项交换贪心，发现交换两个相邻并不会造成其他影响，而对于相邻两人而言，肯定是他们两者的最大值越小越好。于是可以直接假设相邻两项 $(a_x, b_x)$ 和 $(a_y, b_y)$，前面的 $\prod a = k$。 那么 $x$ 排在 $y$ 前面的条件是： $$ \frac{k a_x}{b_y} < \frac{k a_y}{b_x} $$ 把 $k$ 除掉并去分母可得： $$ a_x b_x < a_y b_y $$ 直接按这个排序即可。

由于c/c++ 代码需要高精，阅读量较大，这里给出python代码解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 只用讨论左右手乘积最大的那个大臣在最后一位的情况
N = int(input())
left_king, right_king = map(int, input().split())    # 国王的左右手上分别的数字
left_mul = left_king    # left_mul来记录“已经确认不会是最后一个人”的左手边上的数字

left, right = map(int, input().split())    # 第一个大臣的
for i in range(N - 1):
    left_new, right_new = map(int, input().split())
    if left_new * right_new > left * right:   # 来确认是否是左右手乘积最大的那个大臣
        left_mul *= left
        left, right = left_new, right_new
    else:
        left_mul *= left_new
    print(left_mul//right)

同样的，贪心算法是不能进行回推的，所以往往它会需要一个局部最优解，这里常常会结合到优先队列。

这里给大家介绍一下优先队列，

优先队列

优先队列（Priority Queue）是一种特殊的队列数据结构，其中每个元素都有一个与之相关的优先级。与普通队列不同，优先队列并不是按照插入顺序处理元素的，而是根据元素的优先级来决定处理的顺序。具有更高优先级的元素会被优先处理。

优先队列的特点：

  1. 元素的优先级：每个元素在插入时都会分配一个优先级，通常是一个数字。优先级较高的元素会比优先级较低的元素先被处理。
  2. 访问顺序：在普通队列中，元素按插入顺序处理（FIFO: 先进先出）。而在优先队列中，元素会根据其优先级的高低进行排序，优先级高的元素会先被取出。
  3. 操作：
    • 插入（Push）：将一个新元素及其优先级添加到队列中。
    • 删除（Pop）：从队列中删除并返回优先级最高的元素（优先级数值最小或者最大，取决于实现方式）。

优先队列的内部实现方式是通过堆来实现的，但是我们这里不手写堆，c++的话使用stl中的优先队列，python中使用heapq来调用就可也。

复杂度分析：

  • 插入操作（Push）：对于堆实现的优先队列，插入操作的时间复杂度是O(log n)，因为在最坏的情况下，需要将新元素上浮到合适的位置。
  • 删除操作（Pop）：删除操作的时间复杂度为O(log n)，因为需要将堆顶元素删除，并通过下沉操作恢复堆的性质。
  • 访问最大/最小元素：对于堆实现，访问最大或最小元素的时间复杂度是O(1)，因为堆的根节点始终存储最优先的元素。

C++代码示例

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 <queue>
#include <vector>

using namespace std;

struct Compare { 
bool operator()(int a, int b) 
	{
		return a > b; // 将优先队列变为最小堆 
	} 
};

int main() {
    // 创建一个默认的最大堆优先队列
    priority_queue<int> pq;

    // 向队列中插入元素
    pq.push(10);
    pq.push(20);
    pq.push(15);
    pq.push(30);

    // 输出并删除优先队列中的元素（按照优先级顺序）
    while (!pq.empty()) {
        cout << pq.top() << " ";  // 输出优先队列中的最高优先级元素
        pq.pop();  // 删除该元素
        pq.push(156);
    }
    
    return 0;
}

例题

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $n-1$ 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 种果子，数目依次为 $1$ ， $2$ ， $9$ 。可以先将 $1$ 、 $2$ 堆合并，新堆数目为 $3$ ，耗费体力为 $3$ 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$ ，耗费体力为 $12$ 。所以多多总共耗费体力 $=3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。

思路

显然是贪心+优先队列，每次合并的时候选择果子数目少的堆，再把合并的新堆放入优先队列中。

7. 位运算

{

求某个数二进制的第i位：$x&(1<<i)$

$(1<<i)$ 表示 $2^i$，$(n<<i)$ 表示 $n*2^i$，$(i>>k)&1$ 表示二进制数 $i$ 的从右往左数第 $k$ 位是否为 $1$

二进制中 -x=~x+1；
$lowbit(x)$ 表示返回 $x$ 最后一位为 $1$ 的数

  • $k$ 个相同的数异或和，当$k$ 为奇数，结果为这个数本身，否则为 $0$ 。
  • 任何数与 $0$ 异或是这个数本身。
1
2
3
4
int lowbit(int x)
{
   return x&((~x)+1);
}

}

X 进制：

平时我们所说的10进制数是怎么得出来的呢？
比如10进制数 123: 它是由百位上的1 * 10 * 10 加上 十位上的 2 * 10 加上 个位上的 3 得出来的

关于x进制转10进制：
比如题目中给的：11进制（10）、5进制（4）、2进制（0）
对于i位上的数字 $num[i]$，转换为十进制就是 $num[i]$ *低于i位所有位的进制

            就是10*5*2+4*2+0=108
    再比如：11进制（1）、5进制（2）、2进制（0）       
     
            就是1*5*2+2*2+0=14

进制转换

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
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
const int N = 101001;

string a, b;
map<char, int> q;
int tra10(int n, string s)
{
    int ns = s.size();
    int k = 1;
    int res = 0;
    for (int i = ns - 1; i >= 0; i--)
    {
        if (s[i] >= 'A' && s[i] <= 'F')
            res += (q[s[i]] * k);
        else
            res += (s[i] - '0') * k;
        k *= n;
    }
    return res;
}
void output(stack<int> s)
{
    while (!s.empty())
    {
        if (s.top() >= 10)
        {
            cout << (char)(s.top() + 'A' - 10);
        }
        else
            cout << s.top();
        s.pop();
    }
}
void work(int n, int r)
{
    stack<int> s;
    while (n)
    {
        s.push(n % r);
        n /= r;
    }
    output(s);
}
int main()
{
    int n, m, ans;
    cin >> n >> a >> m;
    q['A'] = 10;
    q['B'] = 11;
    q['C'] = 12;
    q['D'] = 13;
    q['E'] = 14;
    q['F'] = 15;
    int n_10 = tra10(n, a);
    // cout << n_10;
    work(n_10, m);
    return 0;
}

8. 动态规划

一、动态规划四步法（万能套路）

  1. 定义状态
    明确dp[i]或dp[i][j]表示什么含义

  2. 确定转移方程
    找出dp[i]与之前状态的关系（最重要的一步）

  3. 初始化
    给初始状态赋基准值（如dp[0] = 0）

  4. 确定计算顺序
    保证计算当前状态时，所需的前驱状态都已计算过

二、线性DP - 最长递增子序列（LIS）

问题描述

给定数组nums，求最长严格递增子序列长度
示例：[10,9,2,5,3,7,101,18] → 最长[2,3,7,101]，长度为4

解法1：O(n²)模板（必背）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i]表示以nums[i]结尾的LIS长度
    int res = 1;
    
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    return res;
}

解法2：O(nlogn)优化（进阶）

1
2
3
4
5
6
7
8
9
10
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails; // tails[k]存储长度为k+1的子序列最小末尾
    
    for(int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if(it == tails.end()) tails.push_back(num);
        else *it = num;
    }
    return tails.size();
}

三、背包DP - 0/1背包

问题描述

给定物品重量w[]和价值v[]，背包容量W，每个物品只能选0或1次，求最大价值

标准模板（空间优化版）

1
2
3
4
5
6
7
8
9
10
int knapsack(vector<int>& w, vector<int>& v, int W) {
    vector<int> dp(W + 1, 0); // dp[j]表示容量j时的最大价值
    
    for(int i = 0; i < w.size(); i++) {
        for(int j = W; j >= w[i]; j--) { // 必须逆向枚举！
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

四步法分析：

  1. 状态定义：dp[j]表示容量为j时的最大价值
  2. 转移方程：dp[j] = max(不选当前物品, 选当前物品)
  3. 初始化：dp[0]=0，其他初始为0
  4. 计算顺序：外层遍历物品，内层逆向遍历容量

四、背包DP - 完全背包

问题描述

与0/1背包相同，但物品可以选无限次

模板（与0/1背包仅枚举顺序不同）

1
2
3
4
5
6
7
8
9
10
int knapsack(vector<int>& w, vector<int>& v, int W) {
    vector<int> dp(W + 1, 0);
    
    for(int i = 0; i < w.size(); i++) {
        for(int j = w[i]; j <= W; j++) { // 正向枚举！
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

关键区别：

  • 0/1背包：内层逆向枚举（防止重复选择）
  • 完全背包：内层正向枚举（允许重复选择）

五、实战技巧

  1. Debug检查清单：

    • 是否正/逆向枚举搞错？
    • 数组大小是否足够？
    • 边界条件是否处理？

  2. 记忆口诀：

    • “01背包倒着走，完全背包正着来”
    • “LIS两重循环，二分优化替换”

  3. 经典变形：

    • 背包问题求方案数 → 初始化dp[0]=1，转移用+=
    • 背包问题求具体方案 → 记录转移路径

掌握这两个模型，能解决80%的笔试DP题！建议先手敲模板10遍，再找3道相关题目练习。

蓝桥杯专项总结

1. 🧩 STL（优先级最高）

核心容器/函数

  • vector
    push_back() / pop_back() / size()
  • string
    substr(pos, len) / find(str) / +=
  • queue
    push() / front() / pop()
  • priority_queue
    默认大根堆，小根堆：priority_queue<int, vector<int>, greater<int>>
  • sort(v.begin(), v.end())
    自定义排序：bool cmp(int a, int b) { return a > b; }

⚡ 应用场景

  • 快速实现数组操作（vector）
  • 字符串处理（substr截取子串）
  • 堆优化（Dijkstra算法优先队列）

2. 🔢 排序（STL为主）

关键模板

1
2
3
4
5
6
7
// 自定义结构体排序
struct Node { int x, y; };
bool cmp(Node a, Node b) { 
    if (a.x == b.x) return a.y < b.y;
    return a.x > b.x;
}
sort(v.begin(), v.end(), cmp);

⚡ 应用场景

  • 贪心算法前的预处理
  • 二分查找前的有序化

3. 🔍 二分（必背！）

整数二分模板

1
2
3
4
5
6
7
8
9
10
int l=1;r=n;
int ans;//ans表示当前答案满足时的最优解
while(l<=r) 
{
	int mid=(l+r)>>1;
	if(check(mid))
	   l=mid+1,ans=mid; 
	else r=mid-1; 
}
cout << ans;

实数二分模板

1
2
3
4
5
6
double l=0, r=1e9;
for (int i=0; i<100; i++) { // 精度控制
    double mid = (l + r) / 2;
    if (check(mid)) r = mid;
    else l = mid;
}

⚡ 应用场景

  • 有序数组查找
  • 答案单调时的最优解问题（如：分绳子）

4. ➕ 前缀和与差分

一维核心公式

  • 前缀和：s[i] = s[i-1] + a[i]
  • 差分：diff[l] += c, diff[r+1] -= c

二维差分操作

1
2
3
4
5
// 矩阵区域加减
diff[x1][y1] += c;
diff[x2+1][y1] -= c;
diff[x1][y2+1] -= c;
diff[x2+1][y2+1] += c;

⚡ 应用场景

  • 区间求和（O(1)查询）
  • 多次区间修改后求最终数组

5. 🧮 数学（背公式！）

高频考点

  • 质数判断：试除法（枚举到√n）
  • 筛质数（线性筛，埃氏筛）
  • 快速幂（递归分治）：
    1
    2
    3
    4
    5
    long long qpow(long long a, long long b, long long p) {
        if (b == 0) return 1 % p;
        long long res = qpow(a, b/2, p);
        return b % 2 ? res * res % p * a % p : res * res % p;
    }
  • 最大公约数：__gcd(a, b)（STL自带）
  • 组合数学问题
  • 进制问题

6. 🤝 并查集 + 贪心

并查集模板

1
2
3
4
5
6
7
int father[N];
int find(int x) {
    return father[x] == x ? x : father[x] = find(father[x]);
}
void merge(int a, int b) {
    father[find(a)] = find(b);
}

贪心策略

  • 排序贪心：按权重排序后取最优
  • 区间调度：优先选结束早的

7. 💻 二进制与位运算

常用操作

  • n & 1：判断奇偶
  • n >> 1：等价于 /2
  • a ^ b ^ b = a：交换变量 a = a ^ b; b = a ^ b; a = a ^ b;

⚡ 应用场景

  • 状态压缩（用二进制表示集合）
  • 快速计算乘除2的幂

8. 🐌 动态规划

经典问题

  • 背包问题
    状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
  • 最长递增子序列
    状态转移：dp[i] = max(dp[i], dp[j] + 1) (j < i && a[j] < a[i])

⚡ 技巧

  • 解决「01背包」「斐波那契」等基础模型

📌 策略

  1. 优先掌握：STL > 排序 > 二分 > 前缀和
  2. 代码默写：每天手敲一次二分/快速幂模板
  3. 动态规划：留到最后，只背经典题！

特别鸣谢！文章参考：[云顶数模]、[茶灵山艾府]、[菜鸟教程]