蓝桥杯及其知识体系

以下内容借鉴了参考中的视频和其他部分。当前还在持续更新中.我的代码库参考：lloyd-kai/cpp-lanqiaocup

一放假就有点放纵自我了，不能再堕落下去了，一定要出重拳！o(￣▽￣)o 今天就要吹响开始学习的号角

要想办法能够在节假日和休闲时间尽可能做到自律，而不是三分钟热度

蓝桥杯系列

准备工作

  1. 蓝桥杯使用的C++是11版本的，注意不要使用过多的新语法

  2. #include <bits/stdc++.h> 考试推荐的万能导入头文件，但是工作的时候不要用

字符串

提醒：C语言和C++具有很多相同的函数。

常见的函数及其使用(C语言)

scanf

1
2
3
4
5
scanf("%d %d"，&a,&b); //表示接收两个int类型的输入 并将其赋值给a和b，注意除了字符串以外都要加上& 因为字符串本身就是指针

char s[10];//定义一个字符串数组
scanf("%s",s);// %s读取字符串，并复制给s，但是如果读取字符串的时候读取到空格或者回车就会停止。
printf("%s",s);// 例如输入为Hello tom 输出结果为 Hello

常见的其他标识符

类型 对应标识符
int %d
double %lf
char %c
char[] %s
long long %lld

正则表达式在scanf中的应用

例如

1
2
3
4
5
6
7
int main()
{
	char s[15];
	scanf("%[^\n]",s);//这里的正则表达式的意思是只要不是回车就读进去，非常好用
	printf("%s",s);
	return 0;
}

strcpy

实现字符串复制的功能 具体看 C/C++参考文档 官网如下cppreference.com

strcat

实现字符串拼接的功能，函数原型：

1
char *strcat(char *restrict dest, const char *restrict src );

strcmp

实现字符串比较的功能

函数原型

1
int strcmp(const char *lhs, const char *rhs );

strlen

测量字符串长度

常见的函数及其使用(C++)

cin与cout

它们的作用和scanf与printf一样，但是有一些差别。

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

using namespace std;

int main()
{
	double a,b
	cin>>a>>b;//输入为2 3
	cout<<fixed<<setprecision(3)<<a<<' '<<b<<'\n';//输出为2.000 3.000 这里的setprecision()是设置保留小数位数
    
    
    char ch;
    cin>>ch;//输入为a
    cout<<ch;//输出为a 这种C语言的字符串建议使用scanf与printf 性能更好
    
    
    
    char s[10];
    cin>>s;//输入lan qiao
    cout<<s;//输出为lan  注意cin输入字符串也是遇到空格或者回车就结束 
    
    
    string s;
    getline(cin,s);//输入为lan qiao此函数能获取一行的输入，包括空格
    cout<<s;//输出为lan qiao
    
    //还有获取字符串的方法是是fgets()函数+输入流的方式
    
    
    string str[10];//cin的好处就是能直接将输入的数据放入容器中
	for(int i = 0;i<10;i++)
	{
		cin>>str[i];//将输入的字符串写入到str[i]中
	}
    
    return 0;
}

可以看见，虽然cin与cout在参数传递的时候不需要指定参数类型(自动判断变量类型), 但是cout对于浮点数和自定义的输出格式不如printf，而且cin与cout的性能相对于scanf与printf较低——由于cin和cout需要自动判断变量类型等内部原因，读写效率比scanf和printf更低，一般建议在考试时使用scanf与printf,而且需要注意：要么在一个程序中使用cin与cout,要么使用scanf与printf,不推荐两者混合使用。

那有没有什么办法提高cin与cout的速度呢？有，那就是取消同步流.建议使用C++风格的输入与输入函数的时候就加上这一行代码。

示例如下

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
	//取消同步流
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	//其他操作不变
	int x;
	cin>>x;
	cout<<s;
	
	return 0;
}

应用及题型

字母与数字的映射关系：

比如题目规定出现A代表10，B代表11，就要想到A的ASCII编码是97，B的编码是98，a的ASCII编码是65，找对应关系。
怎么找呢？这样看，比如数字10代表A，A是A到Z字母集的开头，对应的数也应该是是数集的开头(这里指的是10),那么映射的函数就是f(n)=n−c+′A′f(n)=n-c+'A' 其中n是输入的数字，c是数集的开头，'A’是字母集的开头，得到的结果是字母

1
2
3
4
5
6
7
8
9
10
//数字映射为字母 10代表A  11代表B
if(n>=10)
{
	printf("%c",n-10+'A');//这样n为11就打印B，12就打印C，反之同理
}
//字母映射为数字   ASCII编码中字符0-9对应编码为48-57.
if(c>'A')
{
	printf("%d",c-'A'+10);
}

字母的大小写转换

  1. 用ASCII码实现

原理：字符A减去字符a会变为数字32.

1
2
3
4
5
6
7
8
9
//小写转大写
char a = 'a';
printf("%c",a+('A'-'a'));//大写A比小写a少‘32’，但是不能直接写32或者'32'(直接写就会整形提升)，而是写('A'-'a')，
//

//大写转化为小写同理
char b = 'B';
printf("%c",b-('A'-'a'));

示例：将输入的字符串大写转小写，小写转大写

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 <cctype> 
#include <iostream>
using namespace std;

char convertedCh(char ch) 
{
	if(islower(ch))//或者是用if('a'<=ch && ch<='z')
	{
		ch = toupper(ch);
	}
	else if(isupper(ch))//或者用if('A'<=ch && ch<='Z')
	{
		ch = tolower(ch);
	}
	return ch;
}

int main()
{
	//将输入的字符串小写变大写，大写变小写
	string s;
	getline(cin,s);
	for(int j = 0;j<s.length();j++)
	{
		s[j] = convertedCh(s[j]);
	}
	cout<<s<<'\n';
	
	return 0;
}

在C/C++语言中规定，未尾以\0结束的字符型数组称为字符串。这里值得强调的是，只有以\0 结束的才能算是字符串，否则只能算作字符型数组。这在C/C++中算是一种标准。也只有以 \0结束的字符数组才能以"%s"的方式用printf输出，否则输出的结果会非常奇怪。自己在char数组上构造一个字符串的时候，忘记在末尾加\0可能会导致访问非法内存的错误。

  1. 用库函数实现

islower和isupper是C++标准库中的字符分类函数，用于检查一个字符(char)是否为小写字母或大写字母。islower和isupper函数需要包含头文件<cctype>,也可用万能头包含。函数返回值为bool类型.tolower(char ch)可以将ch转化为小写字母，如果ch不是大写字母就不进行操作。toupper同理，将ch转为大写字母。

示例

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 <cctype> 
#include <iostream>
using namespace std;

int main()
{

	char ch1 = 'a';
	if(islower(ch1)) 
	{
		cout<<ch1<<"是小写字母"<<endl;
		char ch3 = toupper(ch1);//注意如果直接在cout中输入toupper(ch1)会默认将其转为int类型，所以需要用char类型的变量接收
		cout<<ch3<<"是大写字母"<<endl;
	}
    
	char ch2 = 'A';
	if(isupper(ch2))
	{
		cout<<ch2<<"是大写字母"<<endl;
		char ch4 = tolower(ch2);
		cout<<ch4<<"是小写字母"<<endl;
	}
	
	return 0;
}

例题1：判断一个数是奇数还是偶数，但是至少10000位_(:з」∠)_ ？

分析：如果这个数%2==0 就是偶数，关键在于这个数数量级太大，long long也存不下，这个时候需要将其作为“字符”来看待，可以用string 或者是char[] 数组，观察可知，判断奇偶数的关键其实在于最后一位的数字，只要其为偶数，那么整个数为偶数，反之就是奇数.找最后一位就需要用strlen获取字符串的长度了，代码示例如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <cstring>
//如果你用的是C就导入stdio.h和string.h C++的导入上述的方库
char s[10001]
int main()
{
	int len;
	scanf("%s",s);
	len = strlen(s);
	if((s[len-1]-'0')%2 == 0)
	{
		printf("是偶数");
	}
	else
	{
		printf("是奇数");
	}
    return 0;
}

例题2：反转输出字符串

分析：这个很简单，用C语言实现就是从后往前遍历char[]数组并输出，这里就需要使用strlen()函数获取到字符串的长度.C++string类有reverse函数，可以直接反转字符串。

例题3：输出最后一个单词的长度

关键在于遍历读取每一个单词直到读取到文件末尾，这里就使用到C语言中的文件读取，而scanf在读取的过程中如果使用的是scanf("%s",s) 就会持续读取直到为空格，如果读取到文本末尾会返回EOF的值，我们就需要使用这个返回值帮助我们读取到最后一个单词。示例如下

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
#include <cstring>
char s[10001]
int main()
{
	while(scanf("%s",s)!=EOF)//读取到最后一个单词的时候才会退出 
	{
		continue;
	}
	printf("%d\n",strlen(s));
	return 0;
}

刷题练习

题库 - 蓝桥云课

  • 编号1

日期

经典题型1 找闰年

分析：年份非整百且能被4整除的为闰年和年份能被400整除的是闰年

用C语言表示为

1
2
3
4
if(year % 400 == 0||(year % 100 != 0 && year %4 == 0 ) ) //这里有个小技巧，先将判断量小的放前面再将判断量大的放后面，优化一定的时间。
{
    return true;
}

经典题型2：星期几

分析：经常会遇到别人问你几月几号是星期几的情况，如何不查日历，直接用程序算出来呢？一种最简单的方法是，记住很久以前的
某一天是星期几，比如公元1年1月1日是星期一。然后一天一天模拟，算出日期是星期几。这种方法容易理解，但是实现起来代码可能比较长。除此之外，有一个公式可以快速地根据日期计算这一天是星期几，这被称为蔡基姆拉尔森计算公式。

假设星期为w,年份为y，月份为m,日期为d(第几天)，公式为

w=(d+2m+3(m+1)/5+y+y/4−y/100+y/400)%7w = (d + 2m + 3(m+1)/5+y+y/4-y/100+y/400)\%7

然后把计算出来的w加上1就是真正的星期几了,注意每年的1,2月要当成上一年13,14月计算，上述的除法均为整除

1
2
3
4
5
6
7
8
9
int ComDay(int y,int m,int d)
{
    if(m<=2)
    {
        m+=12;
        y--;
	}
	return (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7;
}

经典题型3：计算日期并按格式输出
分析：要考虑到闰年二月时间的变化，不同月份的天数不同。

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
#include <cstdio>
int day[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}
int main()
{
	int y,m,d,k;
	scanf("%d%d%d%d",&y,&m,&d,&k);
	for (int i =1;i <=k;i++){
		1f((y%100!=0 && y%4=0)||y%400=0){
			day[2]= 29;
		}
		else{
			day[2]= 28;
		}
		d++;
		if (d == day[m]){
			d=1;
			m++;
		}
		if (m == 13){
			m=1;
			y++;
		}
	}
	printf("%04d-%02d-%02d\n",y,m,d);
	return 0;
}

技巧：

判断与穷举、范围、布尔值的转化：对于每个月份有多少天这种规律比较复杂的一系列数，用if判断显得臃肿，而将其所有情况写在数组里面，用下标代替判断更为有效。对于字符不能是A-Z这种限定条件，不要用穷举而是用范围的方式(比如if(c>='A' && C<='Z')),这样更加简洁。对于字符串是否相等的问题，有时候不需要flag标志进行判断，而可以用链式方式简化

排序(C++使用sort)

sort是一个C++已经为我们实现好的工具，当我们要用它时，需要先引入一个算法的库一<algorithm>。需要说明的是，sort可以排序任何类型的元素，包括我们自己定义的结构体。我们将需要在C++文件的开始位置加上：#include <algorithm>

函数原型：

  • sort(iterator beg, iterator end, _Pred);

    // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
    // beg 开始迭代器 或者是起始地址
    // end 结束迭代器 或者是结束地址的下一位(arr+size)
    // _Pred 谓词 也就是排序方法 比如greater就是从大到小排序

示例：

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

void myPrint(int val)
{
	cout << val << " ";
}

void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	//sort默认从小到大排序
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	//从大到小排序
	sort(v.begin(), v.end(), greater<int>());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
    
    //对数组排序
    int a[1000];
    for(int i = 0;i<1000;i++)
    {
        a[i] = i;
    }
    sort(a,a+1000);
}

int main() {

	test01();

	system("pause");

	return 0;
}

总结：sort属于开发中最常用的算法之一，需熟练掌握

进阶：自定义 _Pred参数

对于一般的容器谓词可以直接用greater,但是如果是类的排序或者是其他具有多个成员变量的对象的排序呢？这个时候就需要自己定义一个谓词，将需要进行比较的对象作为形参，以某种比较方式进行比较，最后要返回布尔值。为真就会被排到容器前面，假就会排在后面。

示例如下

1
2
3
4
5
6
//返回值必须是bool
bool cmp(int x,int y){
	//这里是比较x与y个位大小，为真返回true，即只要为真的都在前面，为false都在后面。
	return x % 10 > y % 10;
}

使用lambda表达式定义排序方法

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
//在"Sort.cpp"文件内
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void Test_Sort(void)
{
	//初始化
	vector<int> v= {5,1,3,9,11};
	
	//对数组排序
	sort(v.begin(),v.end(),[](const int &u,const int &v) 
	{
		return u>v;
	});
	
	for(int i = 0;i<v.size();i++)
	{
		cout<<v[i]<<' ' ;
	}
}

//在main.cpp文件
int main()
{
    //测试排序函数
	Test_Sort();
    return 0;
}

当然可以用运算符重载直接作为排序方法，但是在考场上不建议使用

还可以加入多个语句进行多次的排序

1
2
3
4
5
6
7
8
9
10
//按照成绩排序，如果第一个成绩相同就按第二个成绩排序，如果第二个成绩相同就按第三个成绩排序
bool cmp_score(Student x,Student y){
	if (x.score[0]!=.score[0]){
		return x.score[0]>y.score[0];
	}
	if (x.score[1]!=.score[1]){
		return x.score[1]>y.score[1];
	}
	return x.score[2]>y.score[2];
}

例题：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
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
  // 请在此输入您的代码
  int size = 0;//获取数组的长度
  cin>>size;

  int num[size];
  for(int i = 0;i<size;i++)
  {
    cin>>num[i];
  }

  sort(num,num+size);
  for(int i = 0;i<size;i++)
  {
    cout<<num[i]<<' ';
  }
  cout<<'\n';
  for(int i = size-1;i>=0;i--) //这里我用了取巧的方法，如果正向遍历是升序，反向遍历就是降序。就只需要排序一次
  {
    cout<<num[i]<<' ';
  }
    
  return 0;
}

初始化列表-C++特性

常用于构造函数和实例对象创建，主要是起到简便的作用。

如下代码所示

1
2
3
4
5
6
struct Student{
	int score;
	string name;
    Student(){}//注意不可省略默认构造函数
	Student(string n,int s):name(n),score(s){}
};

初始化列表的写法是，在构造函数的括号后面加一个冒号，然后按照成员变量（参数）的格式，依次对每一个变量进行初始化，彼此之间用逗号隔开。

注意

  • 函数的参数列表绝对不能省略，像Student():name(n),score(s)这样的写法是不允许的。
  • 如果在初始化完成员变量之后，还有别的事情要做，那可以把代码写在大括号里。但是，就算之后什么都不做，也必须写
    大括号一大括号不能省略！！！

枚举(暴力穷举法)

枚举就是根据提出的问题，列出该问题的所有可能的解，并在逐一列出的过程中，检验每个可能解是否是问题的真正解,如果是就采纳这个解，如果不是就继续判断下一个。
枚举法一般比较直观，容易理解，但由于要检查所有的可能解，因此运行效率较低。

经典枚举题目：求质数、水仙花数等。

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
//求质数
#include <iostream>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int j = n;j<=m;j++)
	{
        if(j==1)
        {
            continue;
        }
		bool is_prime = true;
		for(int i = 2;i<j;i++)
		{
			if(j % i == 0)
			{
				is_prime = fale;
				cout<<j<<"NOT PRIME"<<endl;
				break;
			}
		}
		if(is_prime)
		{
			cout<<j<<"PRIME"<<endl;
		}
	}
	return 0;
}
//还有一种方法是遍历到根号下，也就是大概遍历到一半左右就行。

C++的STL

vector

动态数组.在C++中，vector是一个动态数组容器，可以存储一系列相同类型的元素。它是标准库<vector>中定义的模板类。

常用方法(具体可以看C++ vector 容器 | 菜鸟教程)

函数原型：

  • push_back(ele); //尾部插入元素ele

  • pop_back(); //删除最后一个元素

  • clear(); //删除容器中所有元素

  • size(); //获取vector的长度

  • insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele

  • insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele

  • erase(const_iterator pos); //删除迭代器指向的元素

  • erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素

    蓝桥杯用的最多的就是前4个，后面的遇到了再查资料。

示例：

lloyd-kai/cpp-lanqiaocup: 点击1_3文件夹-其中的Test_vector.h就是

注意：
vector可以构造二维数组吗？可以，比如vector<vector<int> > 但要注意在int> 与> 之间留一个空格，否则有些老编译器无法通过。

例题：蓝桥杯问题编号3226

set

使用前提：引入头文件#include <set>.

set是一种容器，用于存储一组唯的元素，并按照一定的排序规则进行排序。st中的元素是按照升序排序的，默认情况下，它使用元素的比较运算符(<)来进行排序(也就是从小到大排序)。

定义：

1
2
template <class Key,class Compare = less<Key>,class Allocator = allocator<Key>>
class set;
  • Key:表示存储在set中的元素的类型。
  • Compare:表示元素之间的比较函数对象的类型，默认为less,即按照元素的值进行比较。
  • Allocator:表示用于分配内存的分配器类型，默认为allocator.

sett的内部实现使用了红黑树（一种自平衡的二叉搜索树）来存储元素，并保持元素的有序性。这使得在set中插入、删除和查找元素的时间复杂度都是对数时间.
set中的元素是唯一的，即不允许重复的元素存在。当插入一个重复的元素时，set会自动忽略该元素。

multiset

multiset:是一种容器(多重集合)，它与set类似，用于存储一组元素，并按照一定的排序规则进行排序。不同之处在于，multiset容器允许存储重复的元素。

unordered_set

无序集合：是一种容器，用于存储一组唯一的元素，并且没有特定的顺序。unordered_set容器使用哈希表来实现元素的存储和访问，因此元素的插入、删除和查找的时间复杂度都是常数时间，即O(1)。同样因为哈希的不稳定性在考试中很少用，但是在leetcode中经常用。

使用示例：

lloyd-kai/cpp-lanqiaocup: 点击1_3文件夹-其中的Test_set.h就是

string

字符串(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
34
35
#include <iostream>
#include <string>

int main() {
    // 声明并初始化字符串
    std::string greeting = "Hello, World!";
    std::cout << "Greeting: " << greeting << std::endl;

    // 使用 size() 获取字符串长度
    std::cout << "Length of the greeting: " << greeting.size() << std::endl;

    // 使用 empty() 检查字符串是否为空
    std::cout << "Is the greeting empty? " << (greeting.empty() ? "Yes" : "No") << std::endl;

    // 使用 operator[] 访问特定位置的字符
    std::cout << "Character at position 7: " << greeting[7] << std::endl;

    // 使用 substr() 获取子字符串
    std::string sub = greeting.substr(7, 5);
    std::cout << "Substring from position 7 with length 5: " << sub << std::endl;

    // 使用 find() 查找子字符串
    std::cout << "Position of 'World' in the greeting: " << greeting.find("World") << std::endl;

    // 使用 replace() 替换字符串中的部分内容
    // 替换 'World' 为 'C++'
    std::string modified = greeting;
    std::string::size_type pos = modified.find("World");
    if (pos != std::string::npos) {
        modified.replace(pos, 5, "C++"); // 从位置 pos 开始，替换 5 个字符为 "C++"
    }
    std::cout << "Modified greeting: " << modified << std::endl;

    return 0;
}

常用的其他函数

  1. getline(cin,s)；读取一行字符串。
  2. c_str():将参数转化为C风格字符串(const char *) ，如果想要使用printf打印string，就需要用c_str将其转化为C语言的字符串。

queue

queue是一种先进先出(FIFO)的数据结构。queue提供了一组函数来操作和访问元素，但它的功能相对较简单。用的多的是priority_queue(也被称为大顶堆)

priority_queue.与普通队列不同，priority_queue中的元素是按照一定的优先级进行排序的。默认情况下，priority queue:按照元素的值从大到小进行排序。当然可以通过重载运算符或者是自定义比较函数修改其比较函数

示例

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
//自定义比较函数
//方法1 重载运算符
struct Compare{
	bool operator()(int a,int b)
	{
		//自定义的比较函数 按照逆序排列
		return a>b; 
	}
	
	//使用自定义函数的方法
	//在需要的地方写 priority_queue<int,vector<int>,Compare>pq;
	//注意两种自定义函数方法对应的初始化队列的格式是不一样的 
}; 

//方法2 自定义比较函数 
void Test_Compare(void)
{
	//自定义比较函数，注意这里使用auto简化函数类型的书写
	auto compare = [](int a,int b){
		//自定义比较函数
		return a>b; 
	} 
	
	//使用自定义比较函数的方法 
	priority_queue<int,vector<int>,decltype(compare)>pq(compare);
}

如果只是想将大顶堆变为小顶堆(从小到大排序)，可以直接用greater<T> 如priority_queue<int,vector<int>,greater<int>> pq;

deque

deque（双端队列）是一种容器，它允许在两端进行高效的插入和删除操作。deque是由一系列连续的存储块（缓沛区）组成的，每个存储块都存储了多个元素。这使得deque能够在两端进行快速的插入和删除操作，而不需要移动其他元素。

队列例题

1.CLZ银行问题 问题编号1113

难点在于对输入字符串的处理和队列的函数使用，注意队列的遍历一般使用边用头(front)输出边用(pop)出队。

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
60
61
62
63
64
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main()
{
  //加快cout与cin的速度
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  //初始化次数
  int count = 0;
  cin>>count;
  //初始化队列
  queue<string>V,N;

  //开始执行相关操作
  while(count--)
  {
    string op;
    cin>>op;
    if(op == "IN")
    {
      //执行队列添加元素
      string name,q;
      cin>>name>>q;
      if(q == "V")
      {
        //VIP队列添加元素
        V.push(name);
      }
      else
      {
        N.push(name);
      }
    }
    else
    {
      //出队操作
      string q;
      cin>>q;
      if(q == "V")
      {
        //VIP队列添加元素
        V.pop();
      }
      else
      {
        N.pop();
      }
    }
  }
  //输出队列中的元素
  while(V.size())
  {
    cout<<V.front()<<endl;
    V.pop();
  }
  while(N.size())
  {
    cout<<N.front()<<endl;
    N.pop();
  }

  return 0;
}

1.合并果子 问题编号741

难点：1. 数据的类型要使用long long 而不是使用int 2. 这里要使用小顶堆+队列的出队入队操作。

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
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;

int main()
{
  //提高速度
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

  //初始化堆数
  int count = 0;
  cin>>count;

  //初始化优先级队列,小顶堆
  priority_queue<ll,vector<ll>,greater<int>> pile;

  for(int i = 0;i<count;i++)
  {
    ll tem = 0;
    cin>>tem;
    pile.push(tem);
  }

  ll num = 0;
  while(pile.size()>=2)
  {
    ll x = pile.top();
    pile.pop();
    ll y = pile.top();
    pile.pop();
    num+=x+y;
    pile.push(x+y);
  }

  cout<<num;
  return 0;
}

1.小蓝吃糖果 问题编号1624

难点在于总结出可行方案的充要条件是所有糖果数量之和-数量最高的一种糖果的数量>=数量最高的一种糖果的数量-1，也就是说，除开数量最多的糖果，其他的糖果要能填满(>=)数量最高的一种糖果形成的“间隔”(也就是先吃数量最高的糖果，然后吃其他种类的)。
还有一个小细节就是糖果之和会很大，需要使用long long避免溢出.

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
#include <iostream>
#include <queue>
using namespace std;
int main()
{
  // 请在此输入您的代码
  ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
  //初始化
  int num = 0;
  cin>>num;

  long long sum = 0;
  priority_queue<int> v;
  for(int i = 0;i<num;i++)
  {
    int temp = 0;
    cin>>temp;
    v.push(temp);
    sum+=temp;
  }

  if(sum-v.top()>=v.top()-1)
  {
    cout<<"Yes";
  }
  else
  {
    cout<<"No";
  }

  return 0;
}

迭代器

C++通过迭代器可以访问集合中的每个元素，迭代器就好像一根手指指向set中的某个元素(迭代器不仅仅可以在set上使用，还可以在其他的STL中使用)
要改变它指向的元素。通过*(这是解引用运算符，不是乘号的意思)操作可以获取迭代器指向的元素。通过+操作让迭代器指向下一个元素，同理-操作让迭代器指向上一个元素。
迭代器的写法比较固定，set<T>::iterator it就定义了一个指向set<T>这种集合的迭代器it,T是任意的数据类型。其中：iterator是固定的写法。begin函数返回容器中起始元素的迭代器，end函数返回容器的尾后迭代器。

用法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <vector>
int main() {
    // 创建一个 vector 容器并初始化
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 使用迭代器遍历 vector
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0
}

重载运算符

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node{
	int x,y;
	bool operator<(const Node & rhs)const {
		if(x == a.x)
		{
			return y<rhs.y;
		}
		else
		{
			return x<rhs.x;
		}
	}
}

operator<表示我们要重载运算符<，可以看成是一个函数名。rhs是“right hand side”的简称，有右操作数的意思，这里我
们定义为一个const引用。因为该运算符重载定义在结构体内部，左操作数就当前调用operator<的对象。
特别要注意，不要漏掉最后的const。const函数表示不能对其数据成员进行修改操作，并且const对象不能调用非const成员
函数，只允许调用const成员函数。
上面重载规定了排序方式为，优先按照x从小到大排序，如果x相同，那么再按照y从小到大排序。经过了<运算符重载的结
构体，我们就可以比较两个Node对象的大小了，因此可以直接储存在set中了。

map

映射：是指两个集合之间的元素的相互对应关系。通俗地说，就是一个元素对应另外一个元素。比如Tom->1,Mary->2.我们称其中的姓名集合({“Tom”,“Mary”}为关键字集合key,班级集合({1,2}为值集合(value),在C++中常用的映射有map。

map是一种关联容器，用于存储一组键值对(key-value pairs),其中每个键(key)都是唯一的。map容器根据键来自动进行排序，并且可以通过键茯速查找对应的值。map容器使用红黑树(Red-Black Tree) 数据结构来实现，具有较快的插入、删除和查找

构造一个映射
现在我们来构造一个映射。
在C++中，我们构造一个map的语句为：map<T1,2>m;。这样我们定义了一个名为m的从T1类型到T2类型的映射。初始的时候m是空映射。比如map<string,int>m构建了一个字符串到整数的映射，这样我们可以把一个字符串和一个整数关联起来。

插入一对映射
在C++中通过insert函数向集合中插入一个新的映射，参数是一个pair。pair是一个标准库类型，定义在头文件utility中。可以看成是有两个成员变量first和second的结构体，并且重载了<运算符(先比较first大小，如果一样再比较second)。当我们创建一个pair时，必须提供两个类型。
我们可以像这样定义一个保存string和int的pair

1
pair<string,int>p;

make_pair(v1,v2)函数返回由v1和v2初始化的pair,类型可以从v1和v2的类型推断出来。
我们向映射中加入新映射对的时候就是通过插入pair来实现的。如果插入的key之前已经存在了，将不会用插入的新的value替代原来的value,也就是这次插入是无效的。

访问映射
在C++中访问映射和数组一样，直接用[]就能访问。比如dict["Tom"]就可以获取"Tom"的班级了。而这里有一个比较神奇的地方，如果没有对"Tom"做过映射的话，此时你访问dict["Tom"],系统将会自动为"Tom"生成一个映射，其value为对应类型的默认值(比如int的默认值是0,string的默认值是空字符串)。并且我们可以之后再给映射赋予新的值，比如dict["Tom"]=3,这样为我们提供了另一种方便的插入手段。实际上，我们常常通过下标访问的方式来插入映射，而不是通过用insert插入一个pair来实现。

判断关键字是否存在

在C++中，如果你想知道某个关键字是否被映射过，你可以直接用count函数。如果关键字存在，返回1，否则会返回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
#include <iostream>
#include <map>
#include <string>

int main() {
    // 创建一个 map 容器，存储员工的姓名和年龄
    std::map<std::string, int> employees;

    // 插入员工信息
    employees["Alice"] = 30;
    employees["Bob"] = 25;
    employees["Charlie"] = 35;

    //查找员工是否存在
    if(employees.count("Alice"))
    {
        cout<<"Alice is a employees"<<endl;
    }
    else
    {
        cout<<"Alice is not a employees"<<endl;
    }
    
    //这里的代码接下文

    return 0;
}

遍历映射

map的迭代器的定义和set差不多，map<T1,T2>::iterator it就定义了一个迭代器，其中T1、T2分别是key和value的类型。
C++通过迭代器可以访问集合中的每个元素。这里迭代器指向的元素是一个pair,有first和second两个成员变量，分别代
表一个映射的key和value.我们用->运算符来获取值，it->first和(*it).first的效果是一样的，就是获取迭代器it指向的pair里first成员的值。

1
2
3
4
5
//这里的代码接上文
// 遍历 map 并打印员工信息
   for (std::map<std::string, int>::iterator it = employees.begin(); it != employees.end(); ++it) {
       std::cout << it->first << " is " << it->second << " years old." << std::endl;
   }

注意：C++中遍历map是按照关键字从小到大遍历的

map里面可以套用set或者是map，主要是用于处理键值对重复的问题，或者也可以使用multimap，此容器可允许存储多个具有相同键的键值对。

扩展：unordered_map

也是map的一种，不同的是unordered_map不会根据键的顺序进行排序，而是使用哈希函数将键映射到存储桶中，所以在增删查改方面速度较快，但是元素的顺序无法保证，且时间复杂度不稳定，在leetcode中有些题目用的较多。

例题

1.快递分拣 问题编号 1531

难点在于直接用map的键访问其值是困难的，那么就可以将所有的值看作是一个“集合”，也就是vector类型，这样就巧妙解决了访问的问题。

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

map<string,vector<string>>mp;
//一个城市对应多个快递单号，这里最好使用vector容器，用map键访问会很麻烦
vector<string>citys;


int main()
{
  //施法前摇
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

  int num = 0;
  cin>>num;

  for(int i = 0;i<num;i++)
  {
    string a,b;
    cin>>a>>b;
    mp[b].push_back(a);
    if(mp[b].size() == 1)
    {
      citys.push_back(b);
    }
  }

  for(const auto &city : citys)
  {
    cout<< city <<' '<<mp[city].size()<<'\n';
    for(const auto &i:mp[city])
    {
      //输出其快递编号
      cout << i <<'\n';
    }
  }

  return 0;
}

stack

栈，是一种满足一定约束的线性数据结构。其约束是：只允许在栈的一端插入或删除元素，这一端被称为栈顶；相对地，我们
把另一端称为栈底。

标准库里面的stack在头文件<stack>里面，它的定义和map、set、vector都大同小异，如果你对前面的标准库已经使用得很熟练了，那么对于stack的使用你也会一目了然。stack<T>s定义了一个储存T类型数据的栈s.标准库的栈除了支持push(),pop()等基本操作以外，还支持top()来获取栈顶元素、empty()判断栈是否为空、size()计算栈中元素的个数。

使用示例 常用的几乎就在以下示例中

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

int main() {
    std::stack<int> s;

    // 向栈中添加元素
    s.push(10);
    s.push(20);
    s.push(30);

    // 打印栈顶元素
    std::cout << "Top element is: " << s.top() << std::endl; // 输出: Top element is: 30

    // 移除栈顶元素
    s.pop();
    std::cout << "After popping, top element is: " << s.top() << std::endl; // 输出: After popping, top element is: 20

    // 检查栈是否为空
    if (!s.empty()) {
        std::cout << "Stack is not empty." << std::endl; // 输出: Stack is not empty.
    }

    // 打印栈的大小
    std::cout << "Size of stack: " << s.size() << std::endl; // 输出: Size of stack: 2

    // 继续移除元素
    s.pop();
    s.pop();

    // 检查栈是否为空
    if (s.empty()) {
        std::cout << "Stack is empty." << std::endl; // 输出: Stack is empty.
    }

    return 0;
}

1.小蓝的括号串1 问题编号2490

读者可以尝试使用栈解决问题。

list

lis的使用频率不高，在做题时极少遇到需要使用lis的情景(因为一般用数组实现链表)。list是一种双向链表容器，它是标准模板库（STL）提供的一种序列容器。list容器以节点(node)的形式存储元素，并使用指针将这些节点链接在一起，形成一个链表结构。

list容器模板接受两个参数：1.T：指定容器中存储的元素类型 2.Allocator(可选)：指定用于分配内存的分配器类型，默认为std:allocator<T>

list容器的特点包括：

  • 双向性：每个节点都包含指向前一个节点和后一个节点的指针，因此可以在常数时间内在链表中的任意位置进行插入、删除和访问操作。
  • 动态大小：链表的大小可以根据需要动态扩展或收缩，不需要预先指定容器的大小。
  • 不连续存储：链表中的节点可以在内存中的任意位置分布，不要求连续存储，因此插入和删除操作不会导致元素的移动。

list容器提供了一系列成员函数和迭代器来操作和访问链表中的元素，包括增加,删除、访问、反转等操作。可以使用迭代器来遍历链表中的元素。

需要注意的是，由于s是双向链表，因此插入和删除操作的时间复杂度是常量时间O(1),但访问和查找操作的时间复杂度是线性时间On),其中n是链表的大小。因此，如果需要频繁进行随机访问操作，可能更适合使用支持随机访问的容器，如vector或deque。

示例(来源：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
34
35
36
37
#include <iostream>
#include <list>

int main() {
    // 创建一个整数类型的列表
    std::list<int> numbers;

    // 向列表中添加元素
    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_back(30);

    // 访问并打印列表的第一个元素
    std::cout << "First element: " << numbers.front() << std::endl;

    // 访问并打印列表的最后一个元素
    std::cout << "Last element: " << numbers.back() << std::endl;

    // 遍历列表并打印所有元素
    std::cout << "List elements: ";
    for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 删除列表中的最后一个元素
    numbers.pop_back();

    // 再次遍历列表并打印所有元素
    std::cout << "List elements after removing the last element: ";
    for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

pair

在C+中，pair是一个模板类，用于表示一对值的组合。它位于<utility>头文件中
pair类模板有两个模板参数，T1和T2,分别表示第一个值和第二个值的类型
pair类有两个成员变量，first和second,分别表示第一个值和第二个值。
pair类还有一些成员函数和特性，例如默认构造函数、带参数的构造函数、比较运算符重载等。使用pair类，你可以方便地将两个值组合在一起,并进行传递、存储和操作。pair是可以嵌套的

pair自带的排序规则是按照first成员进行升序排序。如果first成员相等，则按照second成员进行升序排序。这意味着当你使用标准库中的排序算法(如std:sort)对包含pair对象的容器进行排序时,会根据pair对象的first)成员进行排序。

示例见我的github仓库

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
//这里是部分展示
#pragma once 
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

//定义一个结构体，表示一个人的信息
struct Person
{
	string name;
	int age;
};

void Test_pair(void)
{
	//创建一个存储Person对象的vector容器
	vector<Person> people;
	
	//添加一些Person对象到vector中
	people.push_back({"Alice",25});
	people.push_back({"Bob",30});
	people.push_back({"Charlie",20});
	
	//创建一个存储pair的vector
	vector<pair<Person,int>>scores;
	
	//添加一些元素
	scores.push_back({people[0],90});
	scores.push_back({people[1],85});
	scores.push_back({people[2],95});
	
	//遍历，打印姓名年龄和评分
	for(auto it:scores) {
		cout<<"Name is "<<it.first.name<<'\n';
		cout<<"Age is "<<it.first.age<<'\n';
		cout<<"Score is "<<it.second<<'\n';
    }
}

注意C++11特性里面包括auto自动类型推导+遍历，在考试的时候就不需要写冗长的迭代器了。

递归

递归是计算机编程中应用最广泛的一个技巧，也是比较难理解的一个技巧，所以我们打算花大量的时间来理解递归。所谓递归，就是函数调用函数自身，一个函数在其定义中有直接或者间接调用自身都叫递归。而递归一般都用来解决有重复子问题的问题。我们先来理解直接递归，间接递归非常复杂，用的比较少。下面通过求解！(！代表阶乘)的问题来理解直接递归。我们知道n!=n×(n-1)！，所以我们很容易写下下面的代码。如果仅仅写一个递归式子还是很简单的，但是递归的一个难点就是——边界条件。所谓边界条件，就是在什么情况下，函数不应该再继续调用自身。

1
2
3
4
5
6
7
8
9
//以下就是常见的递归格式
int factorial(int n)
{
    if(n == 1)//递归边界，也就是递归终止条件
    {
        return 1;
    }
	return n*factorial(n-1);//将大问题分解为子问题  使用递归解决子问题
}

经典题型1： 汉诺塔

汉诺问题看似复杂，其实不管是多少，都可以归纳为三个步骤：1. 把n-1个盘子从A移动到B,此时A上只剩下最下面的一个盘子。2. 直接把最后一个盘子从A移动到C。3.把B上的n-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
34
35
36
37
38
#include <iostream>
#include <stack> 
using namespace std;
stack<int> S[3];//汉诺塔的杆子数 
void move(int x,int y)//盘子移动函数 
{
	int temp = S[x].top(); 
	S[x].pop();
	S[y].puish(temp);
	cout<<x<<"-->"<<y<<endl;
}
void hanoi(int A,int B,int C,int n)
{
	if(n == 1)//如果A杆只有一个盘子时 
	{
		move(A,C);//将A杆的盘子直接移动到C 
		return;
	}
	hanoi(A,C,B,n-1); //将A杆盘子经由C移动到B，并减少A杆的盘子数 
	move(A,C);
	hanoi(B,A,C,n-1);//将剩下B杆的盘子经由A移动到C，直到所有的盘子都移动到C。 
}
int main()
{
	int n; 
	cin>>n;
	for(int i = n;i>=1;i--)//演示汉诺塔 
	{
		S[0].push(i);
	}
	hanoi(0,1,2,n);
	while(!S[2].empty())
	{
		cout<<S[2].top()<<" ";
		S[2].pop();
	}
	return 0;
}

深度优先搜索(DFS)

深度优先搜索按照深度优先的方式进行搜索，通俗点说就是“一条路走到黑”。注意，这里的“搜索”不是指的我们平时在文件中或者在网络上查找某些信息，搜索是一种穷举的方式，把所有可行的方案都列出来，不断去尝试，直到找到问题的解。深度优先搜索和递归的区别是：深度优先搜索是一种算法，注重的是思想；而递归是一种基于编程语言的实现方式。深度优先搜索可以用递归实现，并且两者之间有很多相似之处，也就是说递归是我们用计算机编程语言来实现深度优先搜索这个算法的手段。

以走迷宫为例，首先找到起点S,走到每个点时，按照左、下、右、上的顺序尝试。每走到下一个点以后，我们把这个点当做起点S,继续按顺序尝试。如果某个点上下左右四个方向都尝试过，便回到走到这个点之前的点，这一步我们称之为回溯。继续尝试其他方向。直到所有点都尝试过上下左右四个方向。这就好比你自己去走这个迷宫，你也要一个方向一个方向的尝试着走，如果这条路不行，就回头，尝试下一条路，ds的思想和我们直观的想法很类似。只不过，接下来我们需要用程序来完成这个过程。

抽象深度优先搜索

前面用到的fs算法都是比较容易想象出搜索过程的，接下来我们看一些不那么容易想象搜索过程的fs过程，这些问题我们称为抽象形式的dfs.
来看一个非常简单的问题：给定n个整数，要求选出K个数，使得选出来的K个数的和为sum。

我们在搜索的过程中，用S来记录当前选择的数值总和，k来记录选择的数的个数，deep表示当前正在枚举第几个数是否选择。在第一层dfs的时候，我们可以枚举是否选第一个数，如果选第一个数则让S加上第一个数且k加一，dfs进入到下一层；否则fs直接进入到下一层。当然，这里我们还需要借助全局变量、参数或修改数组中元素的值等方式来标识出当前的层数，为了减少篇幅，在下文中就直接忽略掉了。在第二层，对第二个数做同样的处理，dfs的过程中记录已经选取的数的个数，如果已经选取了k个数，判断S值是否等于su.对于每一层，我们都有两个选择一选和不选。不同的选择，都会使得搜索进入完全不同的分支继续搜索。和搜索树有很大的关系。

如果对搜索树和状态有很好的理解，对后面的广度优先搜索和动态规划的学习都有很大的帮助。前面说过，dfs看起来是运行在图上的搜索算法，而前一节给大家展示的dfs过程，我们没有看到图的存在，这就是抽象形式的dfs的特点。我们可以根据搜索状态构建一张抽象的图，图上的一个顶点就是一个状态，而图上的边就是状态之间的转移关系（进一步搜索或回溯）。虽然s是在这张抽象的图上进行的，但我们不必把这张图真正地建立出来。

我们可以认为，一次dfs实际上就是在搜索树上完成了一次深度优先搜索。而在上节中的搜索树里的每一个状态，记录了两个值一和值和个数。对于每个数，我们都有两个选择一选和不选。不同的选择，都会使得搜索进入完全不同的分支继续搜索。而每个状态对应的子树，都是这个状态通过搜索可能达到的状态。

给定n个整数，要求选出K个数，使得选出来的K个数的和为sum。

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
#include <iostream>
using namespace std;
int n,k,sum,ans;
int a[40];
void dfs(int i,int cnt,int s) //cnt为数的个数
{
	if(i == n) //i是层数
	{
		if(cnt == k && s == sum)  //s是数的和
		{
			ans++;
		}
		return;
	}
	dfs(i+1,cnt,s);
	dfs(i+1,cnt+1,s+a[i]);
}
int main()
{	
	//输入数据
	cion>>n>>k>>sum;
	for(int i = 0;i<n;i++) 
	{
		cin>>a[i];
	}
	ans = 0;
	dfs(0,0,0);
    cout<<ans<<endl;
	
	return 0;
}

或者使用搜索策略，简单来说就是当选择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
#include <iostream>
using namespace std;
int n,k,sum,ans;
int a[40];
bool xuan[40];
void dfs(int i,int cnt,int s)
{
	if(s == sum && cnt == k)
	{
		ans++;
	}
	for(int i = 0;i<n;i++)
	{
		if(!xuan[i])
		{
			xuan[i] = 1;
			dfs(s+a[i],cnt+1);
			xuan[i] = 0;
		}
	}
}
int main()
{
	
	//输入数据
	cion>>n>>k>>sum;
	for(int i = 0;i<n;i++) 
	{
		cin>>a[i];
	}
	ans = 0;
	dfs(0,0);
	cout<<ans<<endl;
	
	return 0;
}

深度优先搜索的剪枝策略

此方法是DFS的改进优化，有时是DFS能否满足题目要求时间限制的关键。

剪枝，顾名思义，就是通过一些判断，砍掉搜索树上不必要的子树。有时候，我们会发现某个结点对应的子树的状态都不是我们要的结果，那么我们其实没必要对这个分支进行搜索，砍掉这个子树，就是剪枝。

比如，如果所有的数都是正数，如果一旦发现当前的和值都已经大于sum了，那么之后不管怎么选和值都不可能回到sum了，我们也可以直接终止这个分支的搜索。我们在搜索过程中，一旦发现如果某些状态无论如何都不能找到最终的解，就可以将其“剪枝”了。说白了就是及时止损，

还是之前的那道题，假设从0-29中选择8个数使得和为200，用之前的代码会发现，如果选择的数超过了8，无论怎么选都是无效的答案，那么何不将其剪掉以提高运行效率，修改如下

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 <iostream>
using namespace std;
int n,k,sum,ans;
int a[40];
void dfs(int i,int cnt,int s) //cnt为数的个数
{
    if(cnt > k) //如果已选择的数的个数大于了题目要求的个数
    {
        return;//直接终止这一条分支的搜索
    }
	if(i == n) //i是层数
	{
		if(cnt == k && s == sum)  //s是数的和
		{
			ans++;
		}
		return;
	}
	dfs(i+1,cnt,s);
	dfs(i+1,cnt+1,s+a[i]);
}
int main()
{	
	//输入数据
	cion>>n>>k>>sum;
	for(int i = 0;i<n;i++) 
	{
		cin>>a[i];
	}
	ans = 0;
	dfs(0,0,0);
    cout<<ans<<endl;
	
	return 0;
}
最优性剪枝

对于求最优解的一类问题，通常可以用最优性剪枝，比如在求解迷宫最短路的时候，如果发现当前的步数已经超过了当前最优解，那从当前状态开始的搜索都是多余的，因为这样搜索下去永远都搜不到更优的解。通过这样的剪枝，可以省去大量冗余的计算。此外，在搜索是否有可行解的过程中，一旦找到了一组可行解，后面所有的搜索都不必再进行了，这算是最优性剪枝的一个特例。

有一个n×m大小的迷宫。其中字符S表示起点，字符T表示终点，字符*表示墙壁，字符.表示平地。你需要从S出发走到T,每次只能向上下左右相邻的位置移动，并且不能走出地图，也不能走进墙壁。保证迷宫至少存在一种可行的路径，输出S走到T的最少步数。通常我们会用BFS解决这个问题，搜到的第一个结果就是答案。现在我们考虑用DFS来解决这个问题，第一个搜到的答案ans并不一定是正解，但是正解一定小于等于ans。于是如果当前步数大于等于ans就直接剪枝，并且每找到一个可行的答案，都会更新ans

实现过程

首先定义一些全局变量，n、m为迷宫的行数和列数，maze记录迷宫的地形，vis记录DFS过程中当前位置是否被访问过，dir表示每次枚举的四个方向，as记录当前到达终点的最小的步数，初始值为一个较大的数。

实现一个in函数,判断坐标是否在迷宫中。

我们来实现dfs函数，它有三个参数，x、y为当前位置的坐标，step为当前的步数。分别在函数入口处和出口处更新当前位置是否访问，然后枚举四个方向，如果(tx，ty)满足在边界内、不是墙、没被访问过，就继续扩展，并且步数增加1。

如果当前步数大于等于as就剪枝，因为继续深搜下去不可能更优了。如果当前位置为终点，就更新ans并返回。

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
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdio> 
#include <string>
using namespace std;
int n,m;
string maze[110];//迷宫的地形 
bool vis[110][110];//用矩阵记录当前位置是否被访问 
int dir[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};//每次枚举的四个方向 
int ans = 100000;

//判断每次扩展的位置是不是在迷宫中
bool in(int x,int y) 
{
	return 0<=x && x<n && 0<=y && y<m;
}

//访问函数
void dfs(int x,int y,int step) 
{
	//剪枝情况
	if(step >=ans) 
	{
		return;
	}
	if(maze[x][y] == 'T')
	{
		ans = step;
		return;
	}
	
	vis[x][y] = 1;
	for(int i = 0;i<4;i++)
	{
		int tx = x + dir[i][0];
		int ty = y + dir[i][1];
		if(in(tx.ty) && maze[tx][ty] !='*' && !vis[tx][ty])
		{
			dfs(tx,ty,step+1);
		}
	}
	vis[x][y] = 0;
}

int main()
{
	//测试函数
	cin>>n>>m;
	for(int i = 0;i<n;i++) 
	{
		cin>>maze[i];
	}
	int x,y;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			if(maze[i][j] == 'S')
			{
				x = i,y=j;
			}
		}
	}
	dfs(x,y,0);
	cout<<ans<<endl;
	
	return 0; 
}
重复性剪枝

对于某一些特定的搜索方式，一个方案可能会被搜索很多次，这样是没必要的。
再来看这个问题：给定n个整数，要求选出K个数，使得选出来的K个数的和为sum.
如果搜索方法是每次从剩下的数里选一个数，一共搜到第k层，那么1,2,3这个选取方法能被搜索到6次，这是没必要的，因为我们只关注选出来的数的和，而根本不会关注选出来的数的顺序，所以这里可以用重复性剪枝。

我们规定选出来的数的位置是递增的，在搜索的时候，用一个参数来记录上一次选取的数的位置，那么此次选择我们从这个数之后开始选取，这样最后选出来的方案就不会重复了。

奇偶性剪枝

广度优先搜索(BFS)

队列(queue)是一种线性的数据结构，和栈一样是一种运算受限制的线性表。其限制只允许从表的前端(front)进行删除操作，而在表的后端(rar)进行插入操作。一般允许进行插入的一端我们称为队尾，允许删除的一端称为队首。队列的插入操作又叫入队，队列的删除操作又叫出队。
C++也有实现的STL，示例如下. 注意队列中是没有清空的

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 <queue>
//注意这里没有写using namespace std; 如果你写了 后面调用对应函数可以省略写std::

int main() {
    // 创建一个整数队列
    std::queue<int> q;

    // 向队列中添加元素
    q.push(10);
    q.push(20);
    q.push(30);

    // 打印队列中的元素数量
    std::cout << "队列中的元素数量: " << q.size() << std::endl;

    // 打印队首元素
    std::cout << "队首元素: " << q.front() << std::endl;

    // 打印队尾元素
    std::cout << "队尾元素: " << q.back() << std::endl;

    // 移除队首元素
    q.pop();
    std::cout << "移除队首元素后，队首元素: " << q.front() << std::endl;

    // 再次打印队列中的元素数量
    std::cout << "队列中的元素数量: " << q.size() << std::endl;
    
    //判断队列是否为空
    std::cout << "队列是否为空: "<< q.empty() << std::endl;

    return 0;
}

广度优先搜索，又称宽度优先搜索，简称bfs,我们以后都会用bfs来表示广度优先搜索。与深度优先搜索不同的是，广度优先搜索会先将与起始点距离较近的点搜索完毕，再继续搜索较远的点，而深搜却是沿着一个分支搜到最后。
bfs从起点开始，优先搜索离起点最近的点，然后由这个最近的点扩展其他稍近的点，这样一层一层的扩展，就像水波扩散一样。

这里BFS需要借助队列实现，实现步骤抽象如下

  1. 初始的时候把起始点放到队列中，并标记起点访问。
  2. 如果队列不为空，从队列中取出一个元素x,否则算法结束。
  3. 访问和x相连的所有点v，如果U没有被访问，把v入队，并标记已经访问。
  4. 重复执行步骤2。

代码框架如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bfs(起始点)
{
	将起始点放入队列;
	标记起点访问;
	while(如果队列不为空)
	{
		访问队列中队首元素X;
		删除队首元素;
		for(x 所有相邻点)
		{
			if(该点未被访问过且合法)
			{
				将该点加入队列末尾;
			}
		}
	}
}

动态规划

其实就是后面问题的解答可以由前面问题的解递推而来，这种解法也被称为递推算法。

递推也是经常被使用的一种简单算法。递推是一种用若干步可重复的简单运算来描述复杂问题的方法。递推的特点在于，每一项都和他前面的若干项有一定关联，这种关联一般可以通过递推关系式来表示，可以通过其前面若干项得出某项的数据。对于递推问题的求解一般从初始的一个或若干个数据项出发，通过递推关系式逐步推进，从而得出想要的结果，这种求解问题的方法叫递推法。其中，初始的若干数据项称为边界。

以一个例子引入动态规划的问题
设n封信，所有信都装错的情况为FnF_{n}.当添加第几封信的时候，我们可以直接想到，这封信与前n-1封信中的一封放错，那么我们就有n-1种选择。所以我们就可以得到Fn−1×(n−1)F_{n-1}×(n-1)种情况。
这个时候仿佛已经是最后的答案了，但是我们如果仔细想的话，我们会发现我们疏漏了一种情况。因为前n-1封信都是错排。所以Fn−1F_{n-1}的方案里面不会存在有一封信放在正确的位置。但是如果有一封信放在正确的位置，那么第几封信与他错排，依然是一种方案。这个时候就相当于n-2封信相互错排，前n-1封中的一封信和第几封信错排。所以我们就可以得到Fn−2×(n−1)F_{n-2}×(n-1)的方案数。
到这里，我们已经可以得出这个递推式了，根据乘法原理：Fn=(n−1)(Fn−1十Fn−2)F_{n}=(n-1)(F_{n-1}十F_{n-2}) 我们再想一下，代码中的初始条件，也就是边界值。在只有一封信的时候，不可能装错，那么F1=0F_{1}=0；有两封信的时候，装错的方案数为F2=1F_{2}=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
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e3+9

int f[N];

int main()
{
	int n;
	cin>>n;
	f[1] = 0;
	f[2] = 1;
	for(int i = 3;i<=n;i++)
	{
		f[i] = (f[i-1]+f[i-2]*(i-1));
	}
	cout<<f[n]<<endl;
	ll a = 0,b = 1,c=1;
	for(int i = 3;i<=n;i++)
	{
		c = (a+b)*(i-1);
		a = b;
		b = c;
	}
	if(n!=1)
	{
		cout<<c<<endl;
	}
	else
	{
		cout<<0<<endl;
	}
	return 0;
}

二维递推

例题1：杨辉三角——请求出杨辉三角的第n行，第m项的数字是什么？通过递推式表达出来

1
2
3
4
5
6
7
8
9
# 用数据表示为
/*
1
1 1
1 2 1
1 3 3 1
……
整理出递推式子为:f[i][j] = f[i-1][j-1]+f[i-1][j]
*/

动态规划是编程解题的一种重要手段。1951年美国数学家R.Bellman等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优化原理”，从而创建了解决最优化问题的一种新方法：动态规划。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

查找

库函数只能对数组进行二分查找。对一个数组进行二分查找的前提是这个数组中的元素是单调的，一般为单调不减或者单调不增（需要修改比较函数），例如[1,5,5,9,11] 是单调不减

binary_search是C++标准库中的一个算法函数，用于在已排序的序列（例如数组array或容器vector）
中查找特定元素。它通过二分查找算法来确定序列中是否存在目标元素。函数返回一个bool值，表示目标元素是否存在于序列中。如果需要获取找到的元素的位置，可以使用std:lower bound函数或std:upper_bound函数。

示例

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
//在BiSearch.h文件中
#include <vector>
#include <iostream>
#include <algorithm>  //要使用二分法的函数、lower_bound和upper_bound需要导入算法库
using namespace std;

void Test_BiSearch(void)
{
	vector<int> numbers = {1,3,5,7,9};
	int target = 5;
	bool flag = binary_search(numbers.begin(),numbers.end(),target);
	if(flag)
	{
		cout<<"目标元素"<<target<<"被找到"<<'\n';
	}
}


//在main.cpp文件中
//这里主要负责测试头文件定义的测试函数 
int main()
{
	//测试二分法
	Test_BiSearch() ;
	return 0;
}

lower_bound与upper_bound前提：数组必须为非降序。如果要在非升序的数组中使用，可以通过修改比较函数实现(方法与sort自定义比较函数类似)
lower_bound(st,ed,x)返回地址[st,ed)中第一个大于等于x的元素的地址。地址-首地址=下标
upper_bound(st,ed,x)返回地址[st,ed)中第一个大于x的元素的地址。如果不存在则返回最后一个元素的下一个位置，在vector中即end()。

示例

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
//在BiSearch.h文件中
void Test_bound(void) 
{
	//初始化 
	vector<int> v = {5,1,7,3,10,18,9};
	sort(v.begin(),v.end());
	
	for(int i = 0;i<v.size();i++)
	{
		cout<<i<<' ';
	}
	cout<<'\n';
	
	//找到数组中第一个大于等于8元素的下标
	cout<<(lower_bound(v.begin(),v.end(),8)-v.begin())<<'\n';
	
}
//在main.cpp文件中
//这里主要负责测试头文件定义的测试函数 
int main()
{
	//测试bound
	Test_bound(); 
	return 0;
}

例题：1.二分查找数组元素 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
  // 请在此输入您的代码
  //初始化
  int data[200];
  for(int i = 0;i<200;i++)
  {
    data[i] = 4*i+6;
  }

  int target = 0;
  scanf("%d",&target);
  cout<<(lower_bound(data,data+200,target)-data);//对于数组之类的 begin指的是首地址。其他同理

  return 0;
}

其他常见的库函数

memset

memset()是一个用于设置内存块值的函数。它的原型定义在<cstring>头文件中，函数的声明如下：

1
void * memset(void* ptr,int value,size_t num);

其中：ptr:指向要设置值的内存块的指针。value:要设置的值，通常是一个整数(8位二进制数)。num:要设置的字节数。

函数将ptr指向的内存块的前num个字节设置为value的值。它返回一个指向ptr的指针。通常用于初始化内存块，将其设置为特定的值

示例：将一个整型数组所有元素设置为0

1
2
int arr[10];
memset(arr,0,sizeof(arr));

需要注意的是，memset()函数对于非字符类型(即不是char类型的)的数组可能会产生未定义行为。需要使用遍历将其设置对应的值.memset会将每个byte设置为value,比图 比如说你设置的value为1,类型为int,那么二进制为00000001 00000001 00000001 00000001

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>

int a[5] ;
memset(a,1,sizeof(a));//在可能的情况下最好使用二进制、八进制，十六进制作为value
//示例 memset(a,0x33,sizeof(a))  16进制的33
for(int i = 0;i<5;i++)
{
	cout<<bitset<32>(a[i])<<'\n';//输出结果为00000001
}

swap

swap(T&a,T&b)函数接受两个参数：
1.a:要交换值的第一个变量的引用
2.b:要交换值的第二个变量的引用，
swap()函数通过将第一个变量的值存储到临时变量中，然后将第二个变量的值赋给第一个变量，最后将临时变量的值赋给第二
个变量，实现两个变量值的交换。swap()函数可以用于交换任意类型的变量，包括基本类型(如整数、浮点数等）和自定义类型
(如结构体、类对象等)以下是一个示例，展示如何使用swap()函数交换两个整数的值：

1
2
3
int a = 10;
int b = 20;
std::swap(a,b);

reverse

反转容器中元素顺序的函数,它的原型定义在<algorithm>头文件中

reverse()函数接受两个参数：
1.first:指向容器中要反转的第一个元素的迭代器。
2.last:指向容器中要反转的最后一个元素的下一个位置的迭代器。
reverse()函数将[first,last)范围内的元素顺序进行反转。也就是说，它会将frst,last)范围内的元素按相反的顺序重新排列。
reverse()函数可用于反转各种类型的容器，包括数组、向量、链表等。以下是一个示例，展示如何使用reverse(O函数反转一个整型向量的元素顺序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//在OtherFun.h文件里面
void Test_Reverse(void)
{
	vector<int> v = {1,2,3,4,5};
	reverse(v.begin(),v.end());
	for(int i = 0;i<v.size();i++)
	{
		cout<<v[i]<<' ';
	}
	cout<<'\n';
}
//在main.cpp文件里面
int main()
{
	Test_Reverse(); 
    return 0;
}

需要注意的是，reverse函数只能用于支持双向迭代器的容器，因为它需要能够向前和向后遍历容器中的元素。对于只支持单向迭代器的容器（如前向链表），无法使用reverse函数进行反转。

unique

去除容器中相邻重复元素的函数，需要导入头文件<algorithm>

在上述示例中，std:unique(vec.begin(),vec.end())将整型向量vec中的相邻重复元素去除。最终输出的结果是1 2 3 4 5.需要注意的是，unique()函数只能去除相邻的重复元素，如果容器中存在非相邻的重复元素，则无法去除。如果需要去除所有重复元素，而不仅仅是相邻的重复元素，可以先对容器进行排序，然后再使用unique()函数。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//在OtherFun.h文件里面
void Test_Unique(void)
{
	int a[] = {1,1,2,2,3};
	int n = unique(a,a+5)-a;
	for(int i = 0;i<n;i++)
	{
		cout<<a[i]<<' ' ;
	}
}
//在main.cpp文件里面
int main()
{
	Test_Unique(); //结果为1 2 3
    return 0;
}

全排列

next_permutation函数用于生成当前序列的下一个排列。它按照字典序对序列进行重新排列，如果存在下一个排列，则将当前序列更改为下一个排列，并返回tue;如果当前序列已经是最后一个排列，则将序列更改为第一个排列，并返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//在OtherFun.h文件里面
void Test_permutation(void)
{
	vector<int> v = {1,2,3};
	
	//生成下一个排列
	while(next_permutation(v.begin(),v.end()))
	{
		cout<<"下一个排序";
		for(int i = 0;i<3;i++) 
		{
			cout<<v[i]<<' ';
		}
		cout<<'\n';
	} 
}
//在main.cpp文件里面
int main()
{
	//测试全排列函数 
	Test_permutation();
    return 0;
}

prev_permutation函数与next_permutation函数相反，它用于生成当前序列的上一个排列

最值函数

min(a，b)返回a和b中较小的那个值，只能传入两个值，或传入一个列表(比如min({1,2,3,4})。max同理
min_element(St,ed)返回地址[st,ed)中最小的那个值的地址（迭代器），传入参数为两个地址或迭代器。
max_element(st,ed)返回地址[st,ed)中最大的那个值的地址（迭代器），传入参数为两个地址或迭代器。时间复杂度均为O(n),n为数组大小（由传入的参数决定）

但是要注意的是，返回值类型是size_t 一般用long long接收

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Test_TheValue(void) 
{
	//初始化
	vector<int> v = {5,1,3,4,11} ;
	
	//输出最大的元素 通过*解引用得到值
	cout<<*max_element(v.begin(),v.end()) <<'\n';
}
//在main.cpp文件里面
int main()
{
	//测试最值函数
	Test_TheValue(); //输出结果为11
    return 0;
}

nth_element函数

nth_element(st,k,ed)进行部分排序，返回值为void() 传入参数为三个地址或迭代器。其中第二个参数位置的元素将处于正确位置，其他位置元素的顺序可能是任意的，但前面的都比它小，后面的都比它大。时间复杂度O(n)。

举例：求第三小的数字，对于 a[9]={4,7,6,9,1,8,2,3,5};nth_element(a,a+2,a+9)，将下标为2，也就是第3个数放在正确的位置，求的是第3小的数a[2]。（下标从零开始）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Test_nth(void)
{
	//初始化
	vector<int> v = {5,1,7,3,10,18,9};
	
	//输出最大的元素
	nth_element(v.begin(),v.begin()+3,v.end()) ;//这里找的是第四小的数
	
	for(int i = 0;i<7;i++)
	{
		cout<<v[i]<<' ';
	}
}
//在main.cpp文件里面
int main()
{
	//测试最值函数
	Test_nth();//输出结果为3 1 5 7 9 18 10
    return 0;
}

例题

1.成绩分析 - 蓝桥云课-497

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 <algorithm>
#include <bits/stdc++.h>
using namespace std;
int main()
{
  //人数
  int num  =0;
  cin>>num;

  //成绩初始化
  int arr[num];
  int sum = 0;
  for(int i = 0;i<num;i++)
  {
    cin>>arr[i];
    sum+=arr[i];
  }

  cout<<*max_element(arr,arr+num)<<'\n'<<*min_element(arr,arr+num)<<'\n';
  cout<<fixed<<setprecision(2)<<1.0*sum/num;


  return 0;
}

刷题系列

读者可以参考以下的系列博客有针对的刷题

  1. 算法系列(一)蓝桥杯及其知识体系
  2. 算法系列(三)蓝桥杯_算法高阶(一)
  3. 算法系列(三)蓝桥杯_算法高阶(三)
  4. 算法系列(三)蓝桥杯_算法高阶(二)
  5. 算法系列(二)蓝桥杯_算法基础
  6. 算法系列(四)从零开始的算法刷题生活

参考

  1. 蓝桥杯比赛视频教程（入门学习+算法辅导) 建议看前41节 重点是他讲的知识点，由于他讲题特别快不建议按照他的课刷题，建议自行在蓝桥杯题库中刷题。
  2. 力扣刷题攻略 读者可以在这里参考刷题。
  3. 蓝桥云课C++班，作者谢子杨