蓝桥杯备赛笔记（一）

这里的笔记是关于蓝桥杯关键知识点的记录，有别于基础语法，很多内容只要求会用就行，无需深入掌握。

---

前言

持续更新，量变产生质变

---

一、编程基础

1.1 C++基础格式和版本选择

这里只需要记住使用一个万能头文件即可：

#include <bits/stdc++.h> //什么都能用这个头文件
using namespace std;

基本数据类型：

int x = 3; //整数x
double d = 3.14; //浮点数（小数）
char ch = 'A'; //字符常量'A'
char s[] = "Hello"; //字符串
bool b = true; //布尔值，即真假值b。非0为真，0为假

1.2 输入输出

cin和cout：

#include <bits/stdc++.h> //万能头文件
using namespace std; //全局引用std，std里面包含了cin，cout和endl等等东西
int main(){double a,b;cin >> a >> b;//cin会自动判断变量类型cout << fixed << setprecision(3) <<a << '' << b << '\n';//fixed << setprecision(3)的意思是保留浮点数后面3位return 0;//记住最后return 0
}

fixed << setprecision(3) 意思是保留浮点数后3位

在字符或字符串中直接使用cin：

#include <bits/stdc++.h>
using namespace std;
int main(){char ch;cin >> ch;cout << ch;return 0;
}

以上代码中： 输入：a b 输出：a

#include <bits/stdc++.h>
using namespace std;
int main(){char s[10];cin >> s;cout << s;return 0;
}

以上代码中： 输入：hi nihao 输出：hi
注意！！cin无论是在字符或字符串中输入空格或者换行符就会结束

#include <bits/stdc++.h>
using namespace std;
int main(){string s;getline(cin, s);cout << s;return 0;
}

以上代码中： 输入：hi nihao 输出：hi nihao
所以我们可以结合使用string和getline来消除掉这个cin的缺点

取消同步流：
由于cin和cout自动判断变量的关系，它们的读写效率要比scanf和printf更低。
当数据量大的时候，可能导致程序运行超时，我们可以通过取消同步流来加速cin和cout，加速后效率就差不多了。

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); //取消同步流

1.3 string

使用string需要在头文件包含该库 #include<string>

以下是字符串的一些简介：

1. 字符串管理：string封装了字符串的存储和管理。它自动处理字符串的内存分配和释放，避免了手动管理内存的麻烦。
2. 动态大小调整：string可以根据需要自动调整字符串的大小，在添加或删除字符时，string会自动调整内部的存储容量，确保足够的空间来容纳字符串。
3. 安全性：它提供了越界访问检查，以避免访问超出字符串范围的字符。
4. 迭代器支持：string支持迭代器，可以使用迭代器遍历字符串中的字符，进行字符级别的操作。
5. 兼容性：string是C++标准库的一部分，因此广泛使用。

string的声明和初始化：

#include <bits/stdc++.h>
#include <string>
int main(){//声明并初始化一个字符串std::string str1;//使用字符串字面量初始化字符串std::string str2 = "hello, world!";//使用另一个std::string 对象来初始化字符串std::string str3 = str2;//使用部分字符串初始化字符串std::string str4 = str2.substr(0, 5);//substr(起始位置，长度)//使用字符数组初始化字符串const char* charArray = "Hello";std::string str5(charArray);//使用重复的字符初始化字符串std::string str6(5, 'A');//"AAAAA"重复5次A
}

在C++中，std::string类提供了一个成员函数c_str(),用于返回一个指向以空字符结尾的C风格字符串(即const char*类型)。

字符串的基本操作：

1、获取字符串长度：

std::string str = "Hello, world!";
int length = str.length(); //或者 int length = str.size();
std::cout << "Length: " << length << std::endl;

2、拼接字符串（+或append）：

std::string str1 = "Hello";
std::string str2 = "world";
std::string result1 = str1 + "," + str2;//使用+运算符
std::string result2 = str1.append(",").append(str2);//使用append函数
std::cout << "Result1 = " << result1 << std::endl;
std::cout << "Result2 = " << result2 << std::endl;

3、字符串查找（find）：

std::string str = "Hello, world";
size_t pos = str.find("world"); //查找子字符串位置
if(pos != std::string::npos){ //判断是否不等于-1std::cout << "Substring found at position: " << pos << std::endl;
}
else{std::cout << "Substring not found." << std::endl;
}

4、字符串替换（replace）：

std::string str = "Hello, world";
str.replace(7,5, "Universe"); //替换子字符串
//7是子串起始位置，5是要替换掉的长度
std::cout << "Result: " << str << std::endl;

5、提取子字符串（substr）：

std::string str = "Hello, world";
std::string subStr = str.substr(7,5); //提取子字符串
std::cout << "Substring： " << subStr << std::endl;

6、字符串比较（compare）：

std::string str1 = "Hello";
std::string str2 = "World";
int result = str1.compare(str2);//比较字符串
if(result == 0){std::cout << "String are equal." << std::endl;
} else if(result < 0){std::cout << "String 1 is less than String 2." << std::endl;
} else{std::cout << "String 1 is greater than String 2." << std::endl;
}

string重载了不等号，所以也可以直接使用s1 < s2的方式来比较string的大小，比较的规则是按照字典序大小进行比较。

字典序的比较方法是从小到大一个一个比较，一旦遇到不相等的字符就确定大小关系。

例如：
aaaa < bbbb
azz < baaa

常用的遍历string方法一共有两种：

1. 循环枚举下标
2. auto枚举（其中&表示取引用类型，如果对i修改将会改变原来的值）

string s = "Hello";for(int i = 0; i < s.length(); ++i) cout << s[i];//枚举循环遍历一遍string的对象s
cout << '\n';
for(auto i : s)
{cout << i;i = 'a';//此处的修改无效，因为这个i是拷贝出来的，而不是引用s的//所以这里只是赋值到拷贝出来的i里面，而这个i是在局部变量内，这个for循环结束就消亡了
}
cout << '\n';
//此时s = "Hello"
for(auto &i : s)
{cout << i;//此时再遍历输出s字符串还是Helloi = 'a';//此处修改会改变s的字符值
}
cout << '\n';
//此时s= "aaaaa"
cout << s << '\n';

二、竞赛常用库函数

2.1 排序

sort函数：

sort函数包含在头文件<algorithm>中
在使用前需要使用#include <algorithm>或万能头文件#include <bits/stdc++.h>
sort是C++标准库中的一个函数模板，用于对指定范围内的元素进行排序。
sort算法使用的是快速排序或者类似快速排序的改进算法，具有较好的平均时间复杂度，一般为O(nlogn)。
sort的用法：
sort(起始地址, 结束地址的下一位, *比较函数);
比较函数一般默认用的小于号(<)

#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int a[1000];
int n;
//读取数组大小
cin >> n;
//读取元素
for(int i = 1; i <= n; ++i) cin >> a[i];//对数组进行排序
sort(a+1, a+n+1); //[1, n+1) 左闭右开
//   a[1], a[n+1]//输出
for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
return 0;
}

sort(起始地址, 结束地址的下一位, *比较函数);

#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//初始化v
//这里是模板类vector，需要使用万能头文件或#include <vector>
vector<int> v = {5, 1, 3, 9, 11};//对数组进行排序
sort(v.begin(), v.end());//输出
for(int i = 0; i < v.size(); ++i) cout << v[i] << ' ';
//for (auto i : v)cout << i << ' ';//使用auto进行排序也可以
return 0;
}

由于sort默认用小于号进行排序，如果想要自定义比较规则，可以传入第三个参数，这个参数可以是函数或者lambda表达式。

使用传入第三个参数自定义比较函数：

#include <bits/stdc++.h>
using namespace std;
bool cmp(const int &u, const int &v)
{return u > v;
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//初始化vvector<int> v = {5, 1, 3, 9, 11};//对数组进行排序，降序排序sort(v.begin(), v.end(), cmp);//						传入函数名//输出for(int i = 0; i<v.size(); ++i) cout << v[i] << ' ';return 0;
}

使用lambda自定义比较函数：

#include <bits/stdc++.h>
using namespace std;
int main(){//初始化vvector<int> v = {5, 1, 3, 9, 11};//对数组进行排序，降序排序，这里使用lambda表达式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] << ' ';return 0;
}

在[ ]里面不写东西代表把数组内的东西以拷贝的形式放进去，如果在[ ]内加上&后( [&] )就会变成把v里面的变量都以引用(&)类型的格式放进去。

下面是一个本人觉得很妙的操作：

for(int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];

首先，这里我们需要意识到字符串其实就是一个字符数组。在这段代码行中的" \n"[i == n]巧妙的利用了判断符号来确认for循环是否到结尾了，如果到结尾了此时判断会返回1（真），就会自动输出\n换行。如果没到结尾，即i不等于n，此时返回的是0（假），则输出空格。
在这个字符串中下标为0对应的是" “（空格），下标为1对应的是”\n"（回车换行符）

以下是使用了这个操作的题目：

2.2 最值查找

min和max函数：

min(3, 5) = 3
min({1, 2, 3, 4}) = 1
max(a, b)返回a和b中较大的那个值，只能传入两个值，或传入一个列表。
例如：
max(7, 5) = 7
max({1, 2, 3, 4}) = 4
时间复杂度为O(1),传入参数为数组时时间复杂度为O(n)，n为数组大小。
min和max函数是在最值操作时最常用的操作。

min_element和max_element:

min_element(st, ed)返回地址[st, ed)中最小的那个值的下标(迭代器)，传入参数为两个地址或迭代器。
max_element(st, ed)返回地址[st, ed)中最大的那个值的下标(迭代器)，传入参数为两个地址或迭代器。
时间复杂度均为O(n)，n为数组大小(由传入的参数决定)

//初始化v
vector<int> v = {5, 1, 3, 9, 11};//输出最大的元素，*表示解引用，即通过地址(迭代器)得到值
cout << *max_element(v.begin(), v.end()) << '\n';

nth_element函数:

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

//初始化v
vector<int> v = {5, 1, 7, 3, 10, 18, 9};//输出最大的元素，*表示解引用，即通过地址(迭代器)得到值
nth_element(v.begin(), v.begin() + 3, v.end());
//这里v[3]的位置将会位于排序后的位置，其他的任意
for(auto &i : v) cout << i << ' ';

课后题目：

2.3 二分查找

二分法是一种高效的查找方法，它通过将问题的搜索范围一分为二（两边有明显的区别），迭代地缩小搜索范围，直到找到目标或确定目标不存在。
二分法适用于有序数据集合，并且每次迭代可以将搜索范围缩小一半。
二分法本质也是枚举，但和暴力枚举不同，二分法利用数据结构的单调性减少了很多不必要的枚举，从而极大的提高了效率，一般可以将O(n)的枚举优化到O(logn)。
常见的二分类型有：

1. 整数二分
2. 浮点二分
3. 二分答案（最常见）

整数二分查找模板

//找到升序数组a中的x第一次出现的位置
int l = 0, r = 1e9;
//注意这里的判断条件，这样可以保证l，r最终一定收敛到分界点
while(l + 1 != r)//l,r相邻的话退出
{int mid = (l + r) / 2;//如果a为升序，说明mid偏大了，需要减小mid，就只能将r变小，即r = midif(a[mid] >= x) r = mid;else l = mid;//否则l = mid，始终保持在所属区域
}
cout << r << '\n';

浮点二分查找模板

//计算单调函数f(x)的零点
double l = 0, r = 1e9, eps = 1e-6;
//注意这里的判断条件，这样可以保证l，r最终一定收敛到分界点
while(r - l >= eps)//eps是一个极小量，设置为1e-6比较适合
{double mid = (l + r) / 2;//f(x)单调递增，f(mid) >= 0,说明mid偏大了，需要减小mid，就只能将r变小，即r = midif(f(mid) >= 0) r = mid;else l = mid;
}
//最后返回l，r差别不大
cout << r << '\n';

二分答案模板

bool check(int mid)
{bool res = true;//其他内容return res;
}
int main()
{int l = 0, r = 1e9;while(l + 1 != r){int mid = (l + r) / 2;//具体写法需要根据题意修改if(check[mid] >= x) l = mid;else r = mid;
}
cout << l << '\n';//具体输出的内容需要根据题意判断

---

总结